Motivated by recent computational models for redistricting and detection of gerrymandering, we study the following problem on graph partitions. Given a graph G $G$ and an integer k >= 1 $k\ge 1$, a k $k$-district m...
详细信息
Motivated by recent computational models for redistricting and detection of gerrymandering, we study the following problem on graph partitions. Given a graph G $G$ and an integer k >= 1 $k\ge 1$, a k $k$-district map of G $G$ is a partition of V ( G ) $V(G)$ into k $k$ nonempty subsets, called districts, each of which induces a connected subgraph of G $G$. A switch is an operation that modifies a k $k$-district map by reassigning a subset of vertices from one district to an adjacent district;a 1-switch is a switch that moves a single vertex. We study the connectivity of the configuration space of all k $k$-district maps of a graph G $G$ under 1-switch operations. We give a combinatorial characterization for the connectedness of this space that can be tested efficiently. We prove that it is PSPACE-complete to decide whether there exists a sequence of 1-switches that takes a given k $k$-district map into another;and NP-hard to find the shortest such sequence (even if a sequence of polynomial lengths is known to exist). We also present efficient algorithms for computing a sequence of 1-switches that take a given k $k$-district map into another when the space is connected, and show that these algorithms perform a worst-case optimal number of switches up to constant factors.
In this study, a new path-planning algorithm named "Jellyfish Pump Algorithm (JPA)" for the selfreconfiguration of lattice-based self-reconfigurable modular robots (SRMRs) is presented. The JPA is inspired b...
详细信息
In this study, a new path-planning algorithm named "Jellyfish Pump Algorithm (JPA)" for the selfreconfiguration of lattice-based self-reconfigurable modular robots (SRMRs) is presented. The JPA is inspired by the shape changing behavior of a jellyfish during its motion. This motion always satisfies the structural balance of the jellyfish with the help of adaptable and periodic shape changing actions. The proposed approach tries to confirm a physically balanced transformation process of the SRMRs considering external effects such as the gravity. The aim is to conserve the balance by employing a static plus shaped core structure of the robot body during the self-reconfiguration. The mobile modules are allowed to move around this core structure between initial and final configurations. The pivoting cube model is used as the abstraction method of the introduced algorithm. The comparison between pivoting and sliding cube models is presented considering actual world implementation aspects of SRMRs. The JPA is developed as a modification to the well-known self-reconfiguration algorithm of Melt Sort Grow. The JPA allows the robot to reach the final configuration by melting the initial configuration into a balanced intermediate phase having a plus shaped structure instead of a line configuration. The physical balance of the robot is satisfied at each step of the self-reconfiguration process. Appropriate simulations using generic 3D initial configurations have validated the proposed algorithm. Extreme cases such as locomotion and bridge formation are tested with the proposed algorithm considering the robustness and applicability. The time complexity of the JPA is O( n2) for n modules, whereas the balance restrictions enforce the algorithm to generate number of moves less than the square of number of mobile modules. The proposed algorithm was compared with a validated Melt Sort Grow algorithm considering number of moves and time complexity, and the efficiency of the algorithm
This work proposes an automated reconfiguration system to manage two types of faults in any position inside the solar arrays. The faults studied are the short-circuit to ground and the open wires in the string. These ...
详细信息
This work proposes an automated reconfiguration system to manage two types of faults in any position inside the solar arrays. The faults studied are the short-circuit to ground and the open wires in the string. These faults were selected because they severely affect power production. By identifying the affected panels and isolating the faulty one, it is possible to recover part of the power loss. Among other types of faults that the system can detect and locate are: diode short-circuit, internal open-circuit, and the degradation of the internal parasitic serial resistance. The reconfiguration system can detect, locate the above faults, and switch the distributed commutators to recover most of the power loss. Moreover, the system can return automatically to the previous state when the fault has been repaired. A SIMULINK model has been built to prove this automatic system, and a simulated numerical experiment has been executed to test the system response to the faults mentioned. The results show that the recovery of power is more than 90%, and the diagnosis accuracy and sensitivity are both 100% for this numerical experiment.
The problem of reconfiguring two-dimensional VLSI arrays with faults is to find a maximum logical array without faults. The existing algorithms only consider faults associated with processing elements, and all switche...
详细信息
ISBN:
(纸本)9781467345651;9780769549033
The problem of reconfiguring two-dimensional VLSI arrays with faults is to find a maximum logical array without faults. The existing algorithms only consider faults associated with processing elements, and all switches and links are assumed to be fault-free. But switch faults may often occur in the network-on-chips with high density. In this paper, two novel approaches are proposed to tackle the reconfiguration problem of degradable VLSI arrays with switch faults. The first approach extends the well-known existing algorithm with simple pre-processing and row bypass scheme. The second one employs a novel row and column rerouting scheme to maximize the size of the logical array. Simulation results show that the proposed two approaches can effectively generate the logical arrays on the given host array with switch faults, and the second algorithm performs more favorably with the increasing number of the switch faults.
The synthesis of MIMO fault-tolerant control systems under control failures is considered. The solution is written in an analytical form, which makes it possible to synthesize simplified circuit implementations and ad...
详细信息
The synthesis of MIMO fault-tolerant control systems under control failures is considered. The solution is written in an analytical form, which makes it possible to synthesize simplified circuit implementations and adjust coefficients of the fault-tolerant control system in the case of a non-stationary object. A nonlinear medium-range aircraft model was used to verify the results.
Given pair of start and target configurations, each consisting of n pairwise disjoint disks in the plane, what is the minimum number of moves that suffice for transforming the start configuration into the target confi...
详细信息
Given pair of start and target configurations, each consisting of n pairwise disjoint disks in the plane, what is the minimum number of moves that suffice for transforming the start configuration into the target configuration? In one move a disk slides in the plane without intersecting any other disk, so that its center moves along an arbitrary (open) continuous curve. We discuss efficient algorithms for this task and estimate their number of moves under different assumptions on disk radii. For example, with n congruent disks, 3n/2 + O(root n log n) moves always suffice for transforming the start configuration into the target configuration;on the other hand, (1 + 1/15) n - O (root n) moves are sometimes necessary.
Let G be a connected graph, and let V and V' be two n-element subsets of its vertex set V (G). Imagine that we place a chip at each element of V and we want to move them into the positions of V' (V and V' ...
详细信息
ISBN:
(纸本)354032755X
Let G be a connected graph, and let V and V' be two n-element subsets of its vertex set V (G). Imagine that we place a chip at each element of V and we want to move them into the positions of V' (V and V' may have common elements). A move is defined as shifting a chip from v(1) to v(2) (v(1), v(2) epsilon V (G)) on a path formed by edges of G so that no intermediate vertices are occupied. We give upper and lower bounds on the number of moves that are necessary and analyze the computational complexity of this problem under various assumptions: labeled versus unlabeled chips, arbitrary graphs versus the case when the graph is the rectangular (infinite) planar grid, etc. We prove hardness and inapproximability results for several variants of the problem. We also give a linear time algorithm which performs an optimal (minimum) number of moves for the unlabeled version in a tree, and a constant-ratio approximation algorithm for the unlabeled version in a graph. The graph algorithm uses the tree algorithm as a subroutine.
Let G be a connected graph, and let V and V' be two n-element subsets of its vertex set V (G). Imagine that we place a chip at each element of V and we want to move them into the positions of V' (V and V' ...
详细信息
Let G be a connected graph, and let V and V' be two n-element subsets of its vertex set V (G). Imagine that we place a chip at each element of V and we want to move them into the positions of V' (V and V' may have common elements). A move is defined as shifting a chip from v(1) to v(2) (v(1), v(2) epsilon V (G)) on a path formed by edges of G so that no intermediate vertices are occupied. We give upper and lower bounds on the number of moves that are necessary and analyze the computational complexity of this problem under various assumptions: labeled versus unlabeled chips, arbitrary graphs versus the case when the graph is the rectangular (infinite) planar grid, etc. We prove hardness and inapproximability results for several variants of the problem. We also give a linear time algorithm which performs an optimal (minimum) number of moves for the unlabeled version in a tree, and a constant-ratio approximation algorithm for the unlabeled version in a graph. The graph algorithm uses the tree algorithm as a subroutine.
A new reconfiguration scheme, including a reconfiguration algorithm, is proposed in this paper to lift up the fault tolerance and system reconfiguration abilities for the mesh topology. The scheme adds redundancies-sp...
详细信息
A new reconfiguration scheme, including a reconfiguration algorithm, is proposed in this paper to lift up the fault tolerance and system reconfiguration abilities for the mesh topology. The scheme adds redundancies-spare nodes and links-to the mesh network for necessary node replacement. By collocating a suitable number of spare nodes located at the best site of the network and joined by some well-connected spare links, our scheme is simple and yet effective in performing system reconfiguration. To carry out reconfiguration in a more regulated way, a reconfiguration algorithm is provided. The algorithm works dynamically and individually: system reconfiguration starts instantly upon the emergence of a fault and the replacement of a new faulty node-is considered independently from previous replacements. Experimental performance evaluation shows that, with significantly reduced complexity, the proposed reconfiguration scheme is able to achieve desirable reconfiguration rates for the mesh network. (C) 2004 Elsevier Inc. All rights reserved.
暂无评论