The complexity of rerouting shortest paths
From MaRDI portal
Publication:392173
DOI10.1016/j.tcs.2013.09.012zbMath1416.68082arXiv1009.3217OpenAlexW1504277002MaRDI QIDQ392173
Publication date: 13 January 2014
Published in: Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1009.3217
Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Paths and cycles (05C38) Graph algorithms (graph-theoretic aspects) (05C85)
Related Items (22)
Reconfiguration of colorable sets in classes of perfect graphs ⋮ Reconfiguration of regular induced subgraphs ⋮ Reconfiguration on nowhere dense graph classes ⋮ Reconfiguration graphs of shortest paths ⋮ Rerouting shortest paths in planar graphs ⋮ Congestion-Free Rerouting of Flows on DAGs ⋮ Degree-Constrained Subgraph Reconfiguration is in P ⋮ Reconfiguration in bounded bandwidth and tree-depth ⋮ Shifting paths to avoidable ones ⋮ Reconfiguration of vertex-disjoint shortest paths on graphs ⋮ Reconfiguring (non-spanning) arborescences ⋮ Unnamed Item ⋮ Trichotomy for the reconfiguration problem of integer linear systems ⋮ Linear-time algorithm for sliding tokens on trees ⋮ Classification of reconfiguration graphs of shortest path graphs with no induced 4-cycles ⋮ Reconfiguration of satisfying assignments and subset sums: easy to find, hard to connect ⋮ Reconfiguring spanning and induced subgraphs ⋮ Independent Set Reconfiguration in Cographs and their Generalizations ⋮ Reconfiguration of Minimum Steiner Trees via Vertex Exchanges ⋮ A Reconfigurations Analogue of Brooks' Theorem and Its Consequences ⋮ Using contracted solution graphs for solving reconfiguration problems ⋮ On reconfigurability of target sets
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Complexity of independent set reconfigurability problems
- On the complexity of reconfiguration problems
- Shortest paths between shortest paths
- Finding paths between graph colourings: PSPACE-completeness and superpolynomial distances
- Mixing 3-colourings in bipartite graphs
- Connectedness of the graph of vertex-colourings
- Relationships between nondeterministic and deterministic tape complexities
- PSPACE-completeness of sliding-block puzzles and other problems through the nondeterministic constraint logic model of computation
- Motion planning with pulley, rope, and baskets
- Finding paths between 3-colorings
- Shortest Paths between Shortest Paths and Independent Sets
- Reconfiguration of List Edge-Colorings in a Graph
- On the Complexity of Reconfiguration Problems
- The Connectivity of Boolean Satisfiability: Computational and Structural Dichotomies
This page was built for publication: The complexity of rerouting shortest paths
