Parameterized complexity of optimizing list vertex-coloring through reconfiguration

DOI10.1007/978-3-031-27051-2_24OpenAlexW4324009522MaRDI QIDQ6091170

Yuma Tamura, Yusuke Yanagisawa, Akira Suzuki, Xiao Zhou

Publication date: 24 November 2023

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

Full work available at URL: https://doi.org/10.1007/978-3-031-27051-2_24

Mathematics Subject Classification ID

Algorithms in computer science (68Wxx)

Cites Work

• Unnamed Item
• Finding shortest paths between graph colourings
• On the complexity of reconfiguration problems
• Improved upper bounds for vertex cover
• Finding paths between graph colourings: PSPACE-completeness and superpolynomial distances
• Parameterized complexity of the list coloring reconfiguration problem with graph parameters
• Reconfiguration in bounded bandwidth and tree-depth
• Recoloring graphs via tree decompositions
• The coloring reconfiguration problem on specific graph classes
• Using contracted solution graphs for solving reconfiguration problems
• Introduction to reconfiguration
• Reconfiguration graphs for vertex colourings of chordal and chordal bipartite graphs
• Relationships between nondeterministic and deterministic tape complexities
• Decremental optimization of vertex-coloring under the reconfiguration framework
• A Reconfigurations Analogue of Brooks' Theorem and Its Consequences
• The complexity of change
• The List Coloring Reconfiguration Problem for Bounded Pathwidth Graphs
• The Complexity of Bounded Length Graph Recoloring and CSP Reconfiguration
• Finding paths between 3-colorings
• Decremental Optimization of Dominating Sets Under the Reconfiguration Framework
• Incremental optimization of independent sets under the reconfiguration framework
• Incremental optimization of independent sets under the reconfiguration framework

This page was built for publication: Parameterized complexity of optimizing list vertex-coloring through reconfiguration