Rerouting shortest paths in planar graphs
From MaRDI portal
Publication:2403796
DOI10.1016/j.dam.2016.05.024zbMath1369.05041arXiv1204.5613OpenAlexW2464647068MaRDI QIDQ2403796
Publication date: 12 September 2017
Published in: Discrete Applied Mathematics (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1204.5613
Dynamic programming (90C39) Paths and cycles (05C38) Planar graphs; geometric and topological aspects of graph theory (05C10) Distance in graphs (05C12)
Related Items (4)
Reconfiguration of maximum-weight \(b\)-matchings in a graph ⋮ Reconfiguration of vertex-disjoint shortest paths on graphs ⋮ Reconfiguration of Minimum Steiner Trees via Vertex Exchanges ⋮ Using contracted solution graphs for solving reconfiguration problems
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Motion planning with pulley, rope, and baskets
- The complexity of rerouting shortest paths
- On the parameterized complexity of reconfiguration problems
- On the complexity of reconfiguration problems
- Reconfiguration of list edge-colorings in a graph
- Shortest paths between shortest paths
- Reconfiguration on sparse graphs
- Connectedness of the graph of vertex-colourings
- PSPACE-completeness of sliding-block puzzles and other problems through the nondeterministic constraint logic model of computation
- Independent Set Reconfiguration in Cographs and their Generalizations
- The complexity of change
- The List Coloring Reconfiguration Problem for Bounded Pathwidth Graphs
- The Complexity of Bounded Length Graph Recoloring and CSP Reconfiguration
- Finding Shortest Paths Between Graph Colourings
- Reconfiguration over Tree Decompositions
- Finding paths between 3-colorings
- Reconfiguring Independent Sets in Claw-Free Graphs
- Shortest Reconfiguration Paths in the Solution Space of Boolean Formulas
- The Complexity of Dominating Set Reconfiguration
- Solutions to Real-World Instances of PSPACE-Complete Stacking
- Sorting with Complete Networks of Stacks
- Using contracted solution graphs for solving reconfiguration problems.
- The Connectivity of Boolean Satisfiability: Computational and Structural Dichotomies
This page was built for publication: Rerouting shortest paths in planar graphs
