Shortest paths between shortest paths
DOI10.1016/J.TCS.2011.05.021zbMATH Open1225.68136OpenAlexW2040122307MaRDI QIDQ719258FDOQ719258
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
Recommendations
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)
Cites Work
- PSPACE-completeness of sliding-block puzzles and other problems through the nondeterministic constraint logic model of computation
- Mixing 3-colourings in bipartite graphs
- Connectedness of the graph of vertex-colourings
- Finding paths between graph colourings: PSPACE-completeness and superpolynomial distances
- Reconfiguration of List Edge-Colorings in a Graph
- The Connectivity of Boolean Satisfiability: Computational and Structural Dichotomies
- Shortest Paths between Shortest Paths and Independent Sets
- On the Complexity of Reconfiguration Problems
- Finding Paths between Graph Colourings: Computational Complexity and Possible Distances
Cited In (38)
- The complexity of rerouting shortest paths
- Independent set reconfiguration in cographs and their generalizations
- Reconfiguration of Minimum Steiner Trees via Vertex Exchanges
- On reconfiguration graphs of independent sets under token sliding
- Rerouting shortest paths in planar graphs
- On reconfigurability of target sets
- The shortest path reconfiguration problem based on relaxation of reconfiguration rules
- All pairs lightest shortest paths
- Title not available (Why is that?)
- Reconfiguration on nowhere dense graph classes
- 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
- Shortest Paths Avoiding Forbidden Subpaths
- Finding shortest paths between graph colourings
- Shortest paths in reachability graphs
- Finding shortest paths between graph colourings
- The complexity of rerouting shortest paths
- Reconfiguration in bounded bandwidth and tree-depth
- Complexity of independent set reconfigurability problems
- Introduction to reconfiguration
- Computational complexity of jumping block puzzles
- Reconfiguring shortest paths in graphs
- Reconfiguration graphs of shortest paths
- Shortest descending paths through given faces
- 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
- Shortest reconfiguration of sliding tokens on subclasses of interval graphs
- Linear-time algorithm for sliding tokens on trees
- Reconfiguration of list \(L(2,1)\)-labelings in a graph
- Title not available (Why is that?)
- Rerouting shortest paths in planar graphs
- Computational complexity of jumping block puzzles
- Extremal independent set reconfiguration
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)
