Decremental optimization of vertex-coloring under the reconfiguration framework

DOI10.1007/978-3-030-89543-3_30OpenAlexW3209837998MaRDI QIDQ2695300

Yusuke Yanagisawa, Xiao Zhou, Yuma Tamura, Akira Suzuki

Publication date: 30 March 2023

Full work available at URL: https://doi.org/10.1007/978-3-030-89543-3_30

Mathematics Subject Classification ID

Discrete mathematics in relation to computer science (68Rxx)

Related Items (1)

Parameterized complexity of optimizing list vertex-coloring through reconfiguration

Cites Work

• Unnamed Item
• Unnamed Item
• Finding shortest paths between graph colourings
• On the complexity of reconfiguration problems
• Finding paths between graph colourings: PSPACE-completeness and superpolynomial distances
• Some perfect coloring properties of graphs
• Reconfiguration in bounded bandwidth and tree-depth
• Recoloring graphs via tree decompositions
• \(\beta\)-perfect graphs
• Using contracted solution graphs for solving reconfiguration problems
• Introduction to reconfiguration
• Reconfiguration graphs for vertex colourings of chordal and chordal bipartite graphs
• Connectedness of the graph of vertex-colourings
• A Reconfigurations Analogue of Brooks' Theorem and Its Consequences
• The complexity of change
• The Complexity of Bounded Length Graph Recoloring and CSP Reconfiguration
• Finding paths between 3-colorings
• Algorithmic Aspects of Vertex Elimination on Graphs
• Reducibility among Combinatorial Problems
• Decremental Optimization of Dominating Sets Under the Reconfiguration Framework
• Incremental optimization of independent sets under the reconfiguration framework

This page was built for publication: Decremental optimization of vertex-coloring under the reconfiguration framework