Improved Upper Bounds for Partial Vertex Cover
From MaRDI portal
Publication:5302059
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
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
