The Complexity of Bounded Length Graph Recoloring and CSP Reconfiguration

DOI10.1007/978-3-319-13524-3_10zbMath1456.68065OpenAlexW1588967885MaRDI QIDQ2946012

Paul Bonsma, Naomi Nishimura, Amer E. Mouawad, Venkatesh Raman

Publication date: 15 September 2015

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

Full work available at URL: https://doi.org/10.1007/978-3-319-13524-3_10

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Parameterized complexity, tractability and kernelization (68Q27)

Related Items (26)

Finding shortest paths between graph colourings ⋮ Shortest Reconfiguration Paths in the Solution Space of Boolean Formulas ⋮ Parameterized complexity of the list coloring reconfiguration problem with graph parameters ⋮ Reconfiguration on nowhere dense graph classes ⋮ Rerouting shortest paths in planar graphs ⋮ Finding Shortest Paths Between Graph Colourings ⋮ On the Structure of Solution-Graphs for Boolean Formulas ⋮ 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 ⋮ Fast recoloring of sparse graphs ⋮ On the complexity of restoring corrupted colorings ⋮ 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 ⋮ On the parameterized complexity of reconfiguration problems ⋮ Reconfiguration of satisfying assignments and subset sums: easy to find, hard to connect ⋮ Frozen colourings of bounded degree graphs ⋮ Homomorphism Reconfiguration via Homotopy ⋮ Distributed Recoloring ⋮ Algorithms for Coloring Reconfiguration Under Recolorability Constraints ⋮ Frozen (Δ + 1)-colourings of bounded degree 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

This page was built for publication: The Complexity of Bounded Length Graph Recoloring and CSP Reconfiguration