Finding Shortest Paths Between Graph Colourings

DOI10.1007/978-3-319-13524-3_19zbMath1341.68062arXiv1403.6347OpenAlexW2568898402MaRDI QIDQ2946021

Stefan Kratsch, Viresh Patel, Dieter Kratsch, Matthew Johnson, Daniël Paulusma

Publication date: 15 September 2015

Published in: Parameterized and Exact Computation (Search for Journal in Brave)

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

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Coloring of graphs and hypergraphs (05C15) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (7)

A dichotomy theorem for circular colouring reconfiguration ⋮ Shortest Reconfiguration Paths in the Solution Space of Boolean Formulas ⋮ Reconfiguration of dominating sets ⋮ Rerouting shortest paths in planar graphs ⋮ On the complexity of restoring corrupted colorings ⋮ On the parameterized complexity of reconfiguration problems ⋮ Introduction to reconfiguration

Cites Work

• Unnamed Item
• Complexity of independent set reconfigurability problems
• On the parameterized complexity of reconfiguration problems
• Shortest paths between shortest paths
• Finding paths between graph colourings: PSPACE-completeness and superpolynomial distances
• Mixing 3-colourings in bipartite graphs
• Reconfiguration graphs for vertex colourings of chordal and chordal bipartite graphs
• Connectedness of the graph of vertex-colourings
• The complexity of change
• The Complexity of Rerouting Shortest Paths
• Vertex Cover Reconfiguration and Beyond
• The Complexity of Bounded Length Graph Recoloring and CSP Reconfiguration
• Finding paths between 3-colorings
• Approximability of the Subset Sum Reconfiguration Problem
• An Improved Sufficient Condition for Reconfiguration of List Edge-Colorings in a Tree
• Reconfiguration of List Edge-Colorings in a Graph
• Reconfiguring Independent Sets in Claw-Free Graphs
• Reconfiguration of List L(2,1)-Labelings in a Graph
• The Connectivity of Boolean Satisfiability: Computational and Structural Dichotomies

This page was built for publication: Finding Shortest Paths Between Graph Colourings