The complexity of rerouting shortest paths
From MaRDI portal
Publication:392173
DOI10.1016/J.TCS.2013.09.012zbMATH Open1416.68082arXiv1009.3217OpenAlexW1504277002MaRDI QIDQ392173FDOQ392173
Authors: Paul Bonsma 
Publication date: 13 January 2014
Published in: Theoretical Computer Science (Search for Journal in Brave)
Abstract: The Shortest Path Reconfiguration problem has as input a graph G (with unit edge lengths) with vertices s and t, and two shortest st-paths P and Q. The question is whether there exists a sequence of shortest st-paths that starts with P and ends with Q, such that subsequent paths differ in only one vertex. This is called a rerouting sequence. This problem is shown to be PSPACE-complete. For claw-free graphs and chordal graphs, it is shown that the problem can be solved in polynomial time, and that shortest rerouting sequences have linear length. For these classes, it is also shown that deciding whether a rerouting sequence exists between all pairs of shortest st-paths can be done in polynomial time. Finally, a polynomial time algorithm for counting the number of isolated paths is given.
Full work available at URL: https://arxiv.org/abs/1009.3217
Recommendations
Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Paths and cycles (05C38)
Cites Work
- Graph theory
- Relationships between nondeterministic and deterministic tape complexities
- PSPACE-completeness of sliding-block puzzles and other problems through the nondeterministic constraint logic model of computation
- The structure of claw-free graphs
- Mixing 3-colourings in bipartite graphs
- Connectedness of the graph of vertex-colourings
- Finding paths between 3-colorings
- Finding paths between graph colourings: PSPACE-completeness and superpolynomial distances
- Rerouting shortest paths in planar graphs
- Reconfiguration of List Edge-Colorings in a Graph
- Complexity of independent set reconfigurability problems
- The Connectivity of Boolean Satisfiability: Computational and Structural Dichotomies
- On the complexity of reconfiguration problems
- Shortest paths between shortest paths
- Motion planning with pulley, rope, and baskets
- Shortest Paths between Shortest Paths and Independent Sets
- On the Complexity of Reconfiguration Problems
Cited In (36)
- Independent set reconfiguration in cographs and their generalizations
- Reconfiguration of Minimum Steiner Trees via Vertex Exchanges
- Using contracted solution graphs for solving reconfiguration problems
- Rerouting shortest paths in planar graphs
- On reconfigurability of target sets
- Algorithms – ESA 2004
- Congestion-free rerouting of flows on DAGs
- The shortest path reconfiguration problem based on relaxation of reconfiguration rules
- On the complexity of distance-\(d\) independent set reconfiguration
- Reconfiguration on nowhere dense graph classes
- A reconfigurations analogue of Brooks' theorem and its consequences
- On the complexity of an optimal routing tree problem
- Reconfiguration of vertex-disjoint shortest paths on graphs
- Link reversal routing with binary link labels: work complexity
- The complexity of rerouting shortest paths
- Reconfiguration in bounded bandwidth and tree-depth
- Shortest paths between shortest paths
- Shifting paths to avoidable ones
- Reconfiguration of regular induced subgraphs
- Reconfiguring shortest paths in graphs
- Reconfiguration graphs of shortest paths
- Reconfiguration of vertex-disjoint shortest paths on graphs
- Direct routing: Algorithms and complexity
- On the complexity of the shortest-path broadcast problem
- On reconfiguration graphs: an abstraction
- Classification of reconfiguration graphs of shortest path graphs with no induced 4-cycles
- The complexity of routing with few collisions
- The complexity of routing with collision avoidance
- Reconfiguration of colorable sets in classes of perfect graphs
- Reconfiguring (non-spanning) arborescences
- Linear-time algorithm for sliding tokens on trees
- Rerouting shortest paths in planar graphs
- The complexity of the characterization of networks supporting shortest-path interval routing.
- On the computational complexity of continuous routing
- Shortest path reoptimization vs resolution from scratch: a computational comparison
- Degree-constrained subgraph reconfiguration is in P
This page was built for publication: The complexity of rerouting shortest paths
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q392173)
