Vertex Cover Reconfiguration and Beyond

DOI10.1007/978-3-319-13075-0_36zbMath1432.68164arXiv1402.4926OpenAlexW2963273369MaRDI QIDQ2942651

Venkatesh Raman, Naomi Nishimura, Amer E. Mouawad

Publication date: 11 September 2015

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

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

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Parameterized complexity, tractability and kernelization (68Q27)

Related Items

Decremental Optimization of Dominating Sets Under the Reconfiguration Framework ⋮ Shortest Reconfiguration Paths in the Solution Space of Boolean Formulas ⋮ The Complexity of Dominating Set Reconfiguration ⋮ Finding shortest paths between graph colourings ⋮ Shortest Reconfiguration Paths in the Solution Space of Boolean Formulas ⋮ Invitation to combinatorial reconfiguration ⋮ Reconfiguration of dominating sets ⋮ Reconfiguration on nowhere dense graph classes ⋮ Computing the flip distance between triangulations ⋮ Finding Shortest Paths Between Graph Colourings ⋮ Reconfiguration of Vertex Covers in a Graph ⋮ Reconfiguration of maximum-weight \(b\)-matchings in a graph ⋮ Editorial: Special issue on reconfiguration problems ⋮ Unnamed Item ⋮ On girth and the parameterized complexity of token sliding and Token Jumping ⋮ The complexity of dominating set reconfiguration ⋮ On the parameterized complexity of reconfiguration problems ⋮ Reconfiguration of Steiner Trees in an Unweighted Graph ⋮ Introduction to reconfiguration

Cites Work

• Unnamed Item
• Reconfiguration of dominating sets
• Local search: is brute-force avoidable?
• Complexity of independent set reconfigurability problems
• On the parameterized complexity of reconfiguration problems
• On the complexity of reconfiguration problems
• On the parameterized complexity of multiple-interval graph problems
• Some simplified NP-complete graph problems
• Connectedness of the graph of vertex-colourings
• PSPACE-completeness of sliding-block puzzles and other problems through the nondeterministic constraint logic model of computation
• The Complexity of Rerouting Shortest Paths
• The Connectivity of Boolean Satisfiability: Computational and Structural Dichotomies

This page was built for publication: Vertex Cover Reconfiguration and Beyond