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
- Shortest Paths between Shortest Paths and Independent Sets
- The Connectivity of Boolean Satisfiability: Computational and Structural Dichotomies
- The structure of claw-free graphs
Cited in
(42)- On the complexity of an optimal routing tree problem
- Reconfiguration on nowhere dense graph classes
- Reconfiguration graphs of shortest paths
- The complexity of routing with few collisions
- Reconfiguration in bounded bandwidth and tree-depth
- The complexity of routing with collision avoidance
- The complexity of the characterization of networks supporting shortest-path interval routing.
- On reconfigurability of target sets
- Reconfiguration of regular induced subgraphs
- Classification of reconfiguration graphs of shortest path graphs with no induced 4-cycles
- Reconfiguring undirected paths
- Using contracted solution graphs for solving reconfiguration problems
- Direct routing: Algorithms and complexity
- Rerouting shortest paths in planar graphs
- Reconfiguration of colorable sets in classes of perfect graphs
- Reconfiguring (non-spanning) arborescences
- Independent set reconfiguration in cographs and their generalizations
- A reconfigurations analogue of Brooks' theorem and its consequences
- Link reversal routing with binary link labels: work complexity
- The complexity of rerouting shortest paths
- Degree-constrained subgraph reconfiguration is in P
- Rerouting shortest paths in planar graphs
- On the computational complexity of continuous routing
- Linear-time algorithm for sliding tokens on trees
- Congestion-free rerouting of flows on DAGs
- On reconfiguration graphs: an abstraction
- Shortest path reoptimization vs resolution from scratch: a computational comparison
- Reconfiguration of Minimum Steiner Trees via Vertex Exchanges
- Algorithms – ESA 2004
- Shifting paths to avoidable ones
- Reconfiguration of vertex-disjoint shortest paths on graphs
- The shortest path reconfiguration problem based on relaxation of reconfiguration rules
- On the complexity of distance-\(d\) independent set reconfiguration
- Reconfiguring shortest paths in graphs
- Reconfiguration of vertex-disjoint shortest paths on graphs
- Optimal PSPACE-hardness of approximating set cover reconfiguration
- Solution discovery via reconfiguration for problems in P
- Rerouting planar curves and disjoint paths
- Changing induced subgraph isomorphisms under extended reconfiguration rules
- Shortest paths between shortest paths
- Parameterized shortest path reconfiguration
- On the complexity of the shortest-path broadcast problem
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)
