Reconfiguration of connected graph partitions
DOI10.1002/jgt.22856zbMath1525.05151arXiv1902.10765OpenAlexW2916918361MaRDI QIDQ6093138
Oliver Korten, Diane L. Souvaine, Unnamed Author, Unnamed Author, Matias Korman, Csaba D. Tóth, Matthew D. Jones, Unnamed Author, Hugo A. Akitaya
Publication date: 5 October 2023
Published in: Journal of Graph Theory (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1902.10765
Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph algorithms (graph-theoretic aspects) (05C85) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60)
Related Items (2)
Cites Work
- Unnamed Item
- Colored pebble motion on graphs
- Linear-time algorithm for sliding tokens on trees
- Approximating the Maximally Balanced Connected Partition Problem in graphs
- Complexity of token swapping and its variants
- The \((n^ 2-1)\)-puzzle and related relocation problems
- Connectivity preserving transformations for higher dimensional binary images
- Bicolored graph partitioning, or: gerrymandering at its worst
- Optimal redistricting under geographical constraints: why ``pack and crack does not work
- On the complexity of partitioning graphs into connected subgraphs
- A linear-time algorithm for the feasibility of pebble motion on trees
- Optimal partisan districting on planar geographies
- Token sliding on chordal graphs
- Swapping colored tokens on graphs
- Graph puzzles, homotopy, and the alternating group
- Token graphs
- Multi-color pebble motion on graphs
- Fair redistricting is hard
- Swapping labeled tokens on graphs
- A computational approach to unbiased districting
- Weighted Voronoi region algorithms for political districting
- Political districting: from classical models to recent approaches
- The connectivity of token graphs
- Local search algorithms for political districting
- Pushing squares around
- PSPACE-completeness of sliding-block puzzles and other problems through the nondeterministic constraint logic model of computation
- Finding the Shortest Move-Sequence in the Graph-Generalized 15-Puzzle Is NP-Hard
- On-Line Planarity Testing
- Balanced Connected Partitioning of Unweighted Grid Graphs
- Automated Redistricting Simulation Using Markov Chain Monte Carlo
- Distributed Evolutionary Graph Partitioning
- Multi-agent Pathfinding with n Agents on Graphs with n Vertices: Combinatorial Classification and Tight Algorithmic Bounds
This page was built for publication: Reconfiguration of connected graph partitions
