Enumerate and Expand: New Runtime Bounds for Vertex Cover Variants

DOI10.1007/11809678_29zbMath1162.05361OpenAlexW1853034805MaRDI QIDQ3591315

Daniel Mölle, Stefan Richter, Peter Rossmanith

Publication date: 10 September 2007

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

Full work available at URL: https://doi.org/10.1007/11809678_29

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (10)

Quantum speedup for solving the minimum vertex cover problem based on Grover search algorithm ⋮ The connected vertex cover problem in \(k\)-regular graphs ⋮ Complexity and Approximation Results for the Connected Vertex Cover Problem ⋮ Parameterized algorithms for double hypergraph dualization with rank limitation and maximum minimal vertex cover ⋮ Enumerate and expand: Improved algorithms for connected vertex cover and tree cover ⋮ Complexity and algorithms for the connected vertex cover problem in 4-regular graphs ⋮ Fixed-parameter enumerability of cluster editing and related problems ⋮ Complexity and approximation results for the connected vertex cover problem in graphs and hypergraphs ⋮ Vertex and edge covers with clustering properties: Complexity and algorithms ⋮ Bounded-Degree Techniques Accelerate Some Parameterized Graph Algorithms

This page was built for publication: Enumerate and Expand: New Runtime Bounds for Vertex Cover Variants