The Complexity of (List) Edge-Coloring Reconfiguration Problem

DOI10.1007/978-3-319-53925-6_27zbMath1485.68195arXiv1609.00109OpenAlexW3149314075MaRDI QIDQ2980922

Akira Suzuki, Xiao Zhou, Hiroki Osawa, Takehiro Ito

Publication date: 5 May 2017

Published in: WALCOM: Algorithms and Computation (Search for Journal in Brave)

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

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Coloring of graphs and hypergraphs (05C15) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items (2)

Complexity of Hamiltonian cycle reconfiguration ⋮ Introduction to reconfiguration

Cites Work

• Finding shortest paths between graph colourings
• Linear-time algorithm for sliding tokens on trees
• On the complexity of reconfiguration problems
• Reconfiguration of list edge-colorings in a graph
• Finding paths between graph colourings: PSPACE-completeness and superpolynomial distances
• Reconfiguration in bounded bandwidth and tree-depth
• Reconfiguration graphs for vertex colourings of chordal and chordal bipartite graphs
• Relationships between nondeterministic and deterministic tape complexities
• PSPACE-completeness of sliding-block puzzles and other problems through the nondeterministic constraint logic model of computation
• The complexity of change
• The List Coloring Reconfiguration Problem for Bounded Pathwidth Graphs
• The Complexity of Bounded Length Graph Recoloring and CSP Reconfiguration
• Reconfiguration of Cliques in a Graph
• Finding paths between 3-colorings
• Parameterized Complexity of Graph Constraint Logic

This page was built for publication: The Complexity of (List) Edge-Coloring Reconfiguration Problem