Finding shortest paths between graph colourings

DOI10.1007/s00453-015-0009-7zbMath1350.68148OpenAlexW1573626259MaRDI QIDQ309791

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

Publication date: 7 September 2016

Published in: Algorithmica (Search for Journal in Brave)

Full work available at URL: http://dro.dur.ac.uk/15595/1/15595.pdf

zbMATH Keywords

fixed parameter tractabilitygraph colouringgraph algorithmsreconfiguration graphsreconfigurations

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 (17)

Parameterized complexity of the list coloring reconfiguration problem with graph parameters ⋮ Shortest Reconfiguration of Perfect Matchings via Alternating Cycles ⋮ Reconfiguration in bounded bandwidth and tree-depth ⋮ Recognizing graphs close to bipartite graphs with an application to colouring reconfiguration ⋮ Parameterized complexity of optimizing list vertex-coloring through reconfiguration ⋮ Decremental optimization of vertex-coloring under the reconfiguration framework ⋮ The Complexity of (List) Edge-Coloring Reconfiguration Problem ⋮ On a conjecture of Mohar concerning Kempe equivalence of regular graphs ⋮ Trichotomy for the reconfiguration problem of integer linear systems ⋮ Reconfiguring graph homomorphisms on the sphere ⋮ Homomorphism Reconfiguration via Homotopy ⋮ Algorithms for Coloring Reconfiguration Under Recolorability Constraints ⋮ Recognizing Graphs Close to Bipartite Graphs ⋮ Parameterized Complexity of the List Coloring Reconfiguration Problem with Graph Parameters ⋮ Using contracted solution graphs for solving reconfiguration problems ⋮ Introduction to reconfiguration ⋮ Complexity of Coloring Reconfiguration under Recolorability Constraints

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Complexity of independent set reconfigurability problems
• On the parameterized complexity of reconfiguration problems
• On the 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
• Independent Set Reconfiguration in Cographs
• The Complexity of Bounded Length Graph Recoloring and CSP Reconfiguration
• Homomorphism reconfiguration via homotopy
• 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
• Incompressibility through Colors and IDs
• Reconfiguration of List L(2,1)-Labelings in a Graph
• Kernelization Lower Bounds by Cross-Composition
• The Connectivity of Boolean Satisfiability: Computational and Structural Dichotomies

This page was built for publication: Finding shortest paths between graph colourings