Partial Vertex Cover and Budgeted Maximum Coverage in Bipartite Graphs

DOI10.1137/15M1054328zbMath1376.68051OpenAlexW2757966824MaRDI QIDQ5361234

Ojas Parekh, Bugra Caskurlu, Vahan V. Mkrtchyan, K. Subramani and Vahan Mkrtchyan

Publication date: 27 September 2017

Published in: SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/15m1054328

zbMATH Keywords

approximation algorithmNP-completenessvertex coverbudgeted maximum coverage problempartial vertex cover

Mathematics Subject Classification ID

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) Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25)

Related Items (7)

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 fair covering and hitting problems ⋮ On the partial vertex cover problem in bipartite graphs -- a parameterized perspective ⋮ Parameterized and approximation complexity of \textsc{Partial VC Dimension} ⋮ Complexity of the multicut problem, in its vanilla, partial and generalized versions, in graphs of bounded treewidth ⋮ The complexity of mixed-connectivity

Cites Work

• A unified approach to approximating partial covering problems
• On the hardness of approximating minimum vertex cover
• Computing small partial coverings
• Optimization, approximation, and complexity classes
• The budgeted maximum coverage problem
• A primal-dual approximation algorithm for partial vertex cover: Making educated guesses
• The maximum vertex coverage problem on bipartite graphs
• Vertex cover might be hard to approximate to within \(2 - \varepsilon \)
• Using Homogeneous Weights for Approximating the Partial Cover Problem
• Improved Approximation of Maximum Vertex Coverage Problem on Bipartite Graphs
• The Approximability of Partial Vertex Covers in Trees
• Approximation algorithms for partial covering problems
• Reducibility among Combinatorial Problems
• Improved Upper Bounds for Partial Vertex Cover
• Algorithms and Data Structures
• Partial vs. Complete Domination: t-Dominating Set
• Intuitive Algorithms and t-Vertex Cover
• Approximation of Partial Capacitated Vertex Cover
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Partial Vertex Cover and Budgeted Maximum Coverage in Bipartite Graphs