Shortest paths between shortest paths

DOI10.1016/J.TCS.2011.05.021MaRDI QIDQ719258zbMATH OpenOpenAlexFDO

Authors Paul Medvedev, Martin Milanič, Marcin Kamiński

Publication date 10 October 2011

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.tcs.2011.05.021

zbMATH Keywords

diametershortest pathNP-hardreconfigurationreconfigurability

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Distance in graphs (05C12)

Recommendations

• Shortest Paths between Shortest Paths and Independent Sets
• The complexity of rerouting shortest paths
• The complexity of rerouting shortest paths
• Rerouting shortest paths in planar graphs
• Rerouting shortest paths in planar graphs

Cites work

• Connectedness of the graph of vertex-colourings
• Finding Paths between Graph Colourings: Computational Complexity and Possible Distances
• Finding paths between graph colourings: PSPACE-completeness and superpolynomial distances
• Mixing 3-colourings in bipartite graphs
• 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
• Shortest Paths between Shortest Paths and Independent Sets
• The Connectivity of Boolean Satisfiability: Computational and Structural Dichotomies

Cited in

(38)

• The complexity of rerouting shortest paths
• Extremal independent set reconfiguration
• Independent set reconfiguration in cographs and their generalizations
• Reconfiguration of Minimum Steiner Trees via Vertex Exchanges
• Rerouting shortest paths in planar graphs
• On reconfiguration graphs of independent sets under token sliding
• On reconfigurability of target sets
• The shortest path reconfiguration problem based on relaxation of reconfiguration rules
• All pairs lightest shortest paths
• Reconfiguration on nowhere dense graph classes
• scientific article; zbMATH DE number 3105908 (Why is no real title available?)
• A reconfigurations analogue of Brooks' theorem and its consequences
• Shortest reconfiguration of perfect matchings via alternating cycles
• Reconfiguration of vertex-disjoint shortest paths on graphs
• Finding shortest paths between graph colourings
• Shortest paths in reachability graphs
• Finding shortest paths between graph colourings
• Shortest Paths Avoiding Forbidden Subpaths
• Reconfiguration in bounded bandwidth and tree-depth
• Complexity of independent set reconfigurability problems
• The complexity of rerouting shortest paths
• Introduction to reconfiguration
• Reconfiguration graphs of shortest paths
• Computational complexity of jumping block puzzles
• Shortest descending paths through given faces
• Reconfiguring shortest paths in graphs
• Reconfiguration of vertex-disjoint shortest paths on graphs
• Shortest Paths between Shortest Paths and Independent Sets
• On reconfiguration graphs: an abstraction
• Classification of reconfiguration graphs of shortest path graphs with no induced 4-cycles
• Shortest path through random points
• Approximability of the subset sum reconfiguration problem
• Linear-time algorithm for sliding tokens on trees
• Shortest reconfiguration of sliding tokens on subclasses of interval graphs
• Reconfiguration of list \(L(2,1)\)-labelings in a graph
• scientific article; zbMATH DE number 4112412 (Why is no real title available?)
• Rerouting shortest paths in planar graphs
• Computational complexity of jumping block puzzles

This page was built for publication: Shortest paths between shortest paths

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q719258)