Reconfiguration graphs of shortest paths

DOI10.1016/j.disc.2018.07.007zbMath1393.05096arXiv1705.09385OpenAlexW2962755691WikidataQ129453533 ScholiaQ129453533MaRDI QIDQ1660288

Beth Novick, Kossi Edoh, John Asplund, Yulia Hristova, Ruth Haas, Brett M. Werner

Publication date: 15 August 2018

Published in: Discrete Mathematics (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1705.09385

zbMATH Keywords

girthshortest pathsgrid graphreconfiguration graphs

Mathematics Subject Classification ID

Paths and cycles (05C38) Distance in graphs (05C12)

Related Items (3)

Unnamed Item ⋮ Classification of reconfiguration graphs of shortest path graphs with no induced 4-cycles ⋮ Introduction to reconfiguration

Cites Work

• Unnamed Item
• Classifying coloring graphs
• Motion planning with pulley, rope, and baskets
• The complexity of rerouting shortest paths
• On the complexity of reconfiguration problems
• Reconfiguration of list edge-colorings in a graph
• Shortest paths between shortest paths
• Finding paths between graph colourings: PSPACE-completeness and superpolynomial distances
• Mixing 3-colourings in bipartite graphs
• Minimal eigenvalue of the Coxeter Laplacian for the symmetric group
• The \(k\)-dominating graph
• Reconfiguration graphs for vertex colourings of chordal and chordal bipartite 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
• Finding paths between 3-colorings
• Gray code numbers for graphs

This page was built for publication: Reconfiguration graphs of shortest paths