Shortest paths between shortest paths
From MaRDI portal
Publication:719258
DOI10.1016/j.tcs.2011.05.021zbMath1225.68136OpenAlexW2040122307MaRDI QIDQ719258
Martin Milanič, Paul Medvedev, Marcin Kaminski
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
Graph theory (including graph drawing) in computer science (68R10) Distance in graphs (05C12) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)
Related Items (27)
Finding shortest paths between graph colourings ⋮ Reconfiguration of dominating sets ⋮ Reconfiguration on nowhere dense graph classes ⋮ Reconfiguration graphs of shortest paths ⋮ Shortest reconfiguration of sliding tokens on subclasses of interval graphs ⋮ Rerouting shortest paths in planar graphs ⋮ Finding Shortest Paths Between Graph Colourings ⋮ The complexity of rerouting shortest paths ⋮ Reconfiguration in bounded bandwidth and tree-depth ⋮ Reconfiguration of vertex-disjoint shortest paths on graphs ⋮ On reconfiguration graphs of independent sets under token sliding ⋮ Extremal independent set reconfiguration ⋮ Computational complexity of jumping block puzzles ⋮ Complexity of independent set reconfigurability problems ⋮ Unnamed Item ⋮ Approximability of the subset sum reconfiguration problem ⋮ Linear-time algorithm for sliding tokens on trees ⋮ Reconfiguration of list \(L(2,1)\)-labelings in a graph ⋮ On the parameterized complexity of reconfiguration problems ⋮ Classification of reconfiguration graphs of shortest path graphs with no induced 4-cycles ⋮ Reconfiguration of satisfying assignments and subset sums: easy to find, hard to connect ⋮ Computational complexity of jumping block puzzles ⋮ Independent Set Reconfiguration in Cographs and their Generalizations ⋮ Reconfiguration of Minimum Steiner Trees via Vertex Exchanges ⋮ A Reconfigurations Analogue of Brooks' Theorem and Its Consequences ⋮ Introduction to reconfiguration ⋮ On reconfigurability of target sets
Cites Work
- Finding paths between graph colourings: PSPACE-completeness and superpolynomial distances
- Mixing 3-colourings in 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
- Shortest Paths between Shortest Paths and Independent Sets
- Reconfiguration of List Edge-Colorings in a Graph
- Finding Paths between Graph Colourings: Computational Complexity and Possible Distances
- On the Complexity of Reconfiguration Problems
- The Connectivity of Boolean Satisfiability: Computational and Structural Dichotomies
This page was built for publication: Shortest paths between shortest paths
