Reconfiguration of Vertex Covers in a Graph

DOI10.1007/978-3-319-19315-1_15zbMath1401.68250OpenAlexW1156529421MaRDI QIDQ2946052

Xiao Zhou, Takehiro Ito, Hiroyuki Nooka

Publication date: 15 September 2015

Published in: Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-319-19315-1_15

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items (8)

The Complexity of Dominating Set Reconfiguration ⋮ Reconfiguration of dominating sets ⋮ Reconfiguration of maximum-weight \(b\)-matchings in a graph ⋮ Reconfiguration of cliques in a graph ⋮ Unnamed Item ⋮ Reconfiguration of Steiner Trees in an Unweighted Graph ⋮ Introduction to reconfiguration ⋮ On reconfigurability of target sets

Cites Work

• Unnamed Item
• Complexity of independent set reconfigurability problems
• On the parameterized complexity of reconfiguration problems
• On the complexity of reconfiguration problems
• Finding paths between graph colourings: PSPACE-completeness and superpolynomial distances
• Reconfiguration graphs for vertex colourings of chordal and chordal bipartite graphs
• PSPACE-completeness of sliding-block puzzles and other problems through the nondeterministic constraint logic model of computation
• Even-hole-free graphs part I: Decomposition theorem
• Vertex Cover Reconfiguration and Beyond
• Graph Classes: A Survey
• The Connectivity of Boolean Satisfiability: Computational and Structural Dichotomies

This page was built for publication: Reconfiguration of Vertex Covers in a Graph