A parameterized approximation scheme for generalized partial vertex cover

DOI10.1007/978-3-031-38906-1_7MaRDI QIDQ6138992

Zachary Friggstad, Sayan Bandyapadhyay, Ramin Mousavi

Publication date: 16 January 2024

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

zbMATH Keywords

approximation algorithmsfixed parameter tractablepartial vertex cover

Mathematics Subject Classification ID

Algorithms in computer science (68Wxx) Data structures (68P05)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Approximation algorithms for the partition vertex cover problem
• Enumerate and expand: Improved algorithms for connected vertex cover and tree cover
• Computing small partial coverings
• Implementing an efficient fptas for the 0-1 multi-objective knapsack problem
• The hardness of approximation: Gap location
• Fair colorful \(k\)-center clustering
• Algorithms for covering multiple submodular constraints and applications
• Parameterized complexity of Vertex Cover variants
• Vertex cover might be hard to approximate to within \(2 - \varepsilon \)
• On fair covering and hitting problems
• Approximation Algorithms for Maximization Problems Arising in Graph Partitioning
• Approximating Multiobjective Knapsack Problems
• Capacitated Domination and Covering: A Parameterized Perspective
• The importance of being biased
• Nondeterminism within $P^ * $
• A Technique for Obtaining True Approximations for k-Center with Covering Constraints
• On Partial Covering For Geometric Set Systems
• On the Parameterized Complexity of Approximating Dominating Set
• On Approximating (Sparse) Covering Integer Programs
• Algorithms and Data Structures
• Parameterized Algorithms

This page was built for publication: A parameterized approximation scheme for generalized partial vertex cover