Abstract: A rerouting sequence is a sequence of shortest st-paths such that consecutive paths differ in one vertex. We study the the Shortest Path Rerouting Problem, which asks, given two shortest st-paths P and Q in a graph G, whether a rerouting sequence exists from P to Q. This problem is PSPACE-hard in general, but we show that it can be solved in polynomial time if G is planar. To this end, we introduce a dynamic programming method for reconfiguration problems.
Recommendations
Cites work
- scientific article; zbMATH DE number 4060712 (Why is no real title available?)
- scientific article; zbMATH DE number 1390132 (Why is no real title available?)
- Connectedness of the graph of vertex-colourings
- Finding paths between 3-colorings
- Finding shortest paths between graph colourings
- Graph theory
- Independent set reconfiguration in cographs and their generalizations
- Motion planning with pulley, rope, and baskets
- 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
- Reconfiguration over tree decompositions
- Reconfiguring independent sets in claw-free graphs
- Rerouting shortest paths in planar graphs
- Shortest paths between shortest paths
- Shortest reconfiguration paths in the solution space of Boolean formulas
- Solutions to Real-World Instances of PSPACE-Complete Stacking
- Sorting with Complete Networks of Stacks
- The Connectivity of Boolean Satisfiability: Computational and Structural Dichotomies
- The complexity of bounded length graph recoloring and CSP reconfiguration
- The complexity of change
- The complexity of dominating set reconfiguration
- The complexity of rerouting shortest paths
- The list coloring reconfiguration problem for bounded pathwidth graphs
- Using contracted solution graphs for solving reconfiguration problems
Cited in
(11)- Reconfiguring shortest paths in graphs
- The complexity of rerouting shortest paths
- Using contracted solution graphs for solving reconfiguration problems
- The complexity of rerouting shortest paths
- Reconfiguration of maximum-weight \(b\)-matchings in a graph
- The shortest path reconfiguration problem based on relaxation of reconfiguration rules
- Rerouting shortest paths in planar graphs
- Reconfiguration of vertex-disjoint shortest paths on graphs
- Shortest paths between shortest paths
- Reconfiguration of vertex-disjoint shortest paths on graphs
- Reconfiguration of Minimum Steiner Trees via Vertex Exchanges
This page was built for publication: Rerouting shortest paths in planar graphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2403796)
