Rerouting shortest paths in planar graphs

DOI10.1016/j.dam.2016.05.024zbMath1369.05041arXiv1204.5613OpenAlexW2464647068MaRDI QIDQ2403796

Paul Bonsma

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

zbMATH Keywords

dynamic programmingshortest pathplanar graphpolynomial timereroutingreconfiguration problem

Mathematics Subject Classification ID

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