Using contracted solution graphs for solving reconfiguration problems

DOI10.1007/S00236-019-00336-8MaRDI QIDQ2329308zbMATH OpenOpenAlexFDO

Authors Paul Bonsma, Daniël Paulusma

Publication date 17 October 2019

Published in Acta Informatica (Search for Journal in Brave)

Full work available at URL https://drops.dagstuhl.de/opus/volltexte/2016/6435/

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms (68W40) Programming involving graphs or networks (90C35)

Recommendations

• Using contracted solution graphs for solving reconfiguration problems
• The coloring reconfiguration problem on specific graph classes
• Homomorphism reconfiguration via homotopy
• Complexity of coloring reconfiguration under recolorability constraints
• Finding shortest paths between graph colourings

Cites work

• A reconfigurations analogue of Brooks' theorem and its consequences
• Approximability of the subset sum reconfiguration problem
• Complexity of independent set reconfigurability problems
• Connectedness of the graph of vertex-colourings
• Finding paths between 3-colorings
• Finding paths between graph colourings: PSPACE-completeness and superpolynomial distances
• Finding shortest paths between graph colourings
• Graph Classes: A Survey
• Graph theory
• Homomorphism reconfiguration via homotopy
• scientific article; zbMATH DE number 3307330 (Why is no real title available?)
• scientific article; zbMATH DE number 2234775 (Why is no real title available?)
• Independent set reconfiguration in cographs and their generalizations
• Introduction to reconfiguration
• Mixing 3-colourings in bipartite graphs
• On the complexity of reconfiguration problems
• Parameterized complexity of graph constraint logic
• Parameterized complexity of the list coloring reconfiguration problem with graph parameters
• Recognizing Graphs Close to Bipartite Graphs
• Recoloring graphs via tree decompositions
• Reconfiguration graphs for vertex colourings of chordal and chordal bipartite graphs
• Reconfiguration in bounded bandwidth and tree-depth
• Reconfiguration of list \(L(2,1)\)-labelings in a graph
• Reconfiguration of list edge-colorings in a graph
• Reconfiguration over tree decompositions
• Reconfiguring independent sets in claw-free graphs
• Rerouting shortest paths in planar graphs
• Shortest reconfiguration paths in the solution space of Boolean formulas
• Solutions to Real-World Instances of PSPACE-Complete Stacking
• The coloring reconfiguration problem on specific graph classes
• The complexity of bounded length graph recoloring and CSP reconfiguration
• The complexity of change
• The complexity of dominating set reconfiguration
• The complexity of rerouting shortest paths
• The Connectivity of Boolean Satisfiability: Computational and Structural Dichotomies
• The Fine Details of Fast Dynamic Programming over Tree Decompositions
• Treewidth. Computations and approximations
• Using contracted solution graphs for solving reconfiguration problems

Cited in

(4)

• Decremental optimization of vertex-coloring under the reconfiguration framework
• Using contracted solution graphs for solving reconfiguration problems
• Parameterized complexity of optimizing list vertex-coloring through reconfiguration
• Recongo: bounded combinatorial reconfiguration with answer set programming

This page was built for publication: Using contracted solution graphs for solving reconfiguration problems

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2329308)