On Partial Vertex Cover and Budgeted Maximum Coverage Problems in Bipartite Graphs
DOI10.1007/978-3-662-44602-7_2zbMATH Open1417.68149OpenAlexW9203110MaRDI QIDQ3190147FDOQ3190147
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
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
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)
Cited In (10)
- Approximation algorithms for the maximum vertex coverage problem on bounded degree graphs
- On the fixed-parameter tractability of the partial vertex cover problem with a matching constraint in edge-weighted bipartite graphs
- The approximability of partial vertex covers in trees
- Partial vertex cover and budgeted maximum coverage in bipartite graphs
- On the partial vertex cover problem in bipartite graphs -- a parameterized perspective
- Purely combinatorial approximation algorithms for maximum \(k\)-vertex cover in bipartite graphs
- Maximum weighted independent sets with a budget
- Better streaming algorithms for the maximum coverage problem
- Combinatorial approximation of maximum \(k\)-vertex cover in bipartite graphs within ratio 0,7
- Parameterized Algorithms for Partial Vertex Covers in Bipartite Graphs
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)
