The Approximability of Partial Vertex Covers in Trees

DOI10.1007/978-3-319-51963-0_27zbMath1444.68149OpenAlexW2567789782MaRDI QIDQ2971146

Danny Segev, Vahan V. Mkrtchyan, Ojas Parekh, K. Subramani and Vahan Mkrtchyan

Publication date: 4 April 2017

Published in: SOFSEM 2017: Theory and Practice of Computer Science (Search for Journal in Brave)

Full work available at URL: https://www.osti.gov/biblio/1427211

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) Approximation algorithms (68W25)

Related Items (4)

Parameterized Algorithms for Partial Vertex Covers in Bipartite Graphs ⋮ On the fixed-parameter tractability of the partial vertex cover problem with a matching constraint in edge-weighted bipartite graphs ⋮ On the partial vertex cover problem in bipartite graphs -- a parameterized perspective ⋮ Partial Vertex Cover and Budgeted Maximum Coverage in Bipartite Graphs

Cites Work

• On the hardness of approximating minimum vertex cover
• Optimization, approximation, and complexity classes
• A primal-dual approximation algorithm for partial vertex cover: Making educated guesses
• Vertex cover might be hard to approximate to within \(2 - \varepsilon \)
• Using Homogeneous Weights for Approximating the Partial Cover Problem
• On Partial Vertex Cover and Budgeted Maximum Coverage Problems in Bipartite Graphs
• Finding kth paths and p-centers by generating and searching good data structures
• Approximation algorithms for partial covering problems
• Approximation of Partial Capacitated Vertex Cover
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: The Approximability of Partial Vertex Covers in Trees