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

DOI10.1007/978-3-662-44602-7_2MaRDI QIDQ3190147zbMATH OpenOpenAlexFDO

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

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) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Recommendations

• Partial vertex cover and budgeted maximum coverage in bipartite graphs
• The maximum vertex coverage problem on bipartite graphs
• Improved approximation of maximum vertex coverage problem on bipartite graphs
• Parameterized Algorithms for Partial Vertex Covers in Bipartite Graphs
• Constrained minimum vertex cover in bipartite graphs: complexity and parameterized algorithms
• 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
• scientific article; zbMATH DE number 2044921
• Approximation algorithms for the maximum vertex coverage problem on bounded degree graphs
• A 0.821-ratio purely combinatorial algorithm for maximum \(k\)-vertex cover in bipartite graphs

Cited in

(10)

• On the partial vertex cover problem in bipartite graphs -- a parameterized perspective
• Better streaming algorithms for the maximum coverage problem
• On the fixed-parameter tractability of the partial vertex cover problem with a matching constraint in edge-weighted bipartite graphs
• Partial vertex cover and budgeted maximum coverage in bipartite graphs
• Approximation algorithms for the maximum vertex coverage problem on bounded degree graphs
• Combinatorial approximation of maximum \(k\)-vertex cover in bipartite graphs within ratio 0,7
• Purely combinatorial approximation algorithms for maximum \(k\)-vertex cover in bipartite graphs
• Parameterized Algorithms for Partial Vertex Covers in Bipartite Graphs
• The approximability of partial vertex covers in trees
• Maximum weighted independent sets with a budget

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3190147)