The complexity of rerouting shortest paths
From MaRDI portal
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.
Recommendations
Cites work
- Complexity of independent set reconfigurability problems
- Connectedness of the graph of vertex-colourings
- Finding paths between 3-colorings
- Finding paths between graph colourings: PSPACE-completeness and superpolynomial distances
- Graph theory
- Mixing 3-colourings in bipartite graphs
- Motion planning with pulley, rope, and baskets
- On the Complexity of Reconfiguration Problems
- On the complexity of reconfiguration problems
- PSPACE-completeness of sliding-block puzzles and other problems through the nondeterministic constraint logic model of computation
- Reconfiguration of List Edge-Colorings in a Graph
- Relationships between nondeterministic and deterministic tape complexities
- Rerouting shortest paths in planar graphs
- Shortest Paths between Shortest Paths and Independent Sets
- Shortest paths between shortest paths
- The Connectivity of Boolean Satisfiability: Computational and Structural Dichotomies
- The structure of claw-free graphs
Cited in
(36)- The complexity of routing with collision avoidance
- A reconfigurations analogue of Brooks' theorem and its consequences
- Reconfiguring shortest paths in graphs
- Linear-time algorithm for sliding tokens on trees
- Classification of reconfiguration graphs of shortest path graphs with no induced 4-cycles
- Reconfiguration graphs of shortest paths
- Link reversal routing with binary link labels: work complexity
- Using contracted solution graphs for solving reconfiguration problems
- The complexity of rerouting shortest paths
- Direct routing: Algorithms and complexity
- On the complexity of an optimal routing tree problem
- Reconfiguration in bounded bandwidth and tree-depth
- Reconfiguration on nowhere dense graph classes
- On reconfiguration graphs: an abstraction
- Degree-constrained subgraph reconfiguration is in P
- The complexity of the characterization of networks supporting shortest-path interval routing.
- Reconfiguration of regular induced subgraphs
- On reconfigurability of target sets
- Shortest path reoptimization vs resolution from scratch: a computational comparison
- The shortest path reconfiguration problem based on relaxation of reconfiguration rules
- Rerouting shortest paths in planar graphs
- On the complexity of distance-\(d\) independent set reconfiguration
- On the complexity of the shortest-path broadcast problem
- The complexity of routing with few collisions
- Reconfiguration of vertex-disjoint shortest paths on graphs
- On the computational complexity of continuous routing
- Reconfiguration of colorable sets in classes of perfect graphs
- Shortest paths between shortest paths
- Reconfiguring (non-spanning) arborescences
- Algorithms – ESA 2004
- Congestion-free rerouting of flows on DAGs
- Shifting paths to avoidable ones
- Reconfiguration of vertex-disjoint shortest paths on graphs
- Rerouting shortest paths in planar graphs
- Independent set reconfiguration in cographs and their generalizations
- Reconfiguration of Minimum Steiner Trees via Vertex Exchanges
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)
