Shortest Paths between Shortest Paths and Independent Sets

DOI10.1007/978-3-642-19222-7_7zbMath1326.05071arXiv1008.4563OpenAlexW3125407811MaRDI QIDQ3000494

Paul Medvedev, Marcin Kaminski, Martin Milanič

Publication date: 19 May 2011

Published in: Lecture Notes in Computer Science (Search for Journal in Brave)

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

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Paths and cycles (05C38) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph algorithms (graph-theoretic aspects) (05C85) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

Related Items (6)

The connectivity of Boolean satisfiability: dichotomies for formulas and circuits ⋮ The complexity of rerouting shortest paths ⋮ Reconfiguration graphs for vertex colourings of chordal and chordal bipartite graphs ⋮ Complexity of independent set reconfigurability problems ⋮ Reconfiguration of list edge-colorings in a graph ⋮ Shortest paths between shortest paths

Cites Work

• The strong perfect graph theorem
• Finding paths between graph colourings: PSPACE-completeness and superpolynomial distances
• Mixing 3-colourings in bipartite graphs
• Complement reducible 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
• Even-hole-free graphs part II: Recognition algorithm
• Reconfiguration of List Edge-Colorings in a Graph
• Finding Paths between Graph Colourings: Computational Complexity and Possible Distances
• On the Complexity of Reconfiguration Problems
• A Linear Recognition Algorithm for Cographs
• The Connectivity of Boolean Satisfiability: Computational and Structural Dichotomies

This page was built for publication: Shortest Paths between Shortest Paths and Independent Sets