Improved Upper Bounds for Partial Vertex Cover

DOI10.1007/978-3-540-92248-3_22zbMath1202.05108OpenAlexW1525118263MaRDI QIDQ5302059

Joachim Kneis, Alexander Langer, Peter Rossmanith

Publication date: 20 January 2009

Published in: Graph-Theoretic Concepts in Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-540-92248-3_22

zbMATH Keywords

partial vertex cover problem

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Nonnumerical algorithms (68W05) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph algorithms (graph-theoretic aspects) (05C85) Randomized algorithms (68W20)

Related Items

Parameterized Algorithms for Partial Vertex Covers in Bipartite Graphs ⋮ Refined algorithms for hitting many intervals ⋮ On the fixed-parameter tractability of the partial vertex cover problem with a matching constraint in edge-weighted bipartite graphs ⋮ Parameterized algorithms for graph partitioning problems ⋮ Calculating approximation guarantees for partial set cover of pairs ⋮ On the partial vertex cover problem in bipartite graphs -- a parameterized perspective ⋮ Subexponential algorithms for partial cover problems ⋮ Exact algorithms for problems related to the densest \(k\)-set problem ⋮ Efficient algorithms for the \textsc{max~\(k\)-vertex cover problem} ⋮ Parameterized reductions and algorithms for a graph editing problem that generalizes vertex cover ⋮ Parameterized algorithm for eternal vertex cover ⋮ Partial Vertex Cover and Budgeted Maximum Coverage in Bipartite Graphs ⋮ Bounded-Degree Techniques Accelerate Some Parameterized Graph Algorithms ⋮ Pareto Complexity of Two-Parameter FPT Problems: A Case Study for Partial Vertex Cover ⋮ Partial vertex cover on graphs of bounded degeneracy ⋮ Moderately exponential time and fixed parameter approximation algorithms ⋮ Approximating the \textsc{Sparsest} \(k\)-\textsc{Subgraph} in chordal graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Ramsey numbers and an approximation algorithm for the vertex cover problem
• Computing small partial coverings
• Approximation algorithms for combinatorial problems
• A measure & conquer approach for the analysis of exact algorithms
• Random Separation: A New Method for Solving Fixed-Cardinality Optimization Problems
• Color-coding
• Approximation algorithms for partial covering problems
• Fixed-Parameter Tractability and Completeness I: Basic Results
• Algorithms and Data Structures
• Partial vs. Complete Domination: t-Dominating Set
• Intuitive Algorithms and t-Vertex Cover