On Partial Vertex Cover and Budgeted Maximum Coverage Problems in Bipartite Graphs

DOI10.1007/978-3-662-44602-7_2zbMath1417.68149OpenAlexW9203110MaRDI QIDQ3190147

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

Publication date: 15 September 2014

Published in: Advanced Information Systems Engineering (Search for Journal in Brave)

Full work available at URL: https://hal.inria.fr/hal-01402014/file/978-3-662-44602-7_2_Chapter.pdf

zbMATH Keywords

bipartite graphvertex cover problembudgeted maximum coverage problempartial vertex cover problem

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) 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)

Related Items (9)

Approximation algorithms for the maximum vertex coverage problem on bounded degree graphs ⋮ Parameterized Algorithms for Partial Vertex Covers in Bipartite Graphs ⋮ Purely combinatorial approximation algorithms for maximum \(k\)-vertex cover in bipartite graphs ⋮ On the fixed-parameter tractability of the partial vertex cover problem with a matching constraint in edge-weighted bipartite graphs ⋮ Combinatorial approximation of maximum k-vertex cover in bipartite graphs within ratio 0.7 ⋮ On the partial vertex cover problem in bipartite graphs -- a parameterized perspective ⋮ The Approximability of Partial Vertex Covers in Trees ⋮ Maximum Weighted Independent Sets with a Budget ⋮ Better streaming algorithms for the maximum coverage problem

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