Improved approximation of maximum vertex coverage problem on bipartite graphs

DOI10.1137/130931059zbMATH Open1310.90095OpenAlexW2040480264MaRDI QIDQ2935262FDOQ2935262

Authors: Nicola Apollonio, Bruno Simeone 

Publication date: 22 December 2014

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

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

Recommendations

• The maximum vertex coverage problem on bipartite graphs
• Partial vertex cover and budgeted maximum coverage in bipartite graphs
• Approximation algorithms for the maximum vertex coverage problem on bounded degree graphs
• On approximation of max-vertex-cover
• Combinatorial approximation of maximum \(k\)-vertex cover in bipartite graphs within ratio 0,7

zbMATH Keywords

LP roundingtransversal numbervertex coverage

Mathematics Subject Classification ID

Linear programming (90C05) Approximation methods and heuristics in mathematical programming (90C59) Combinatorial optimization (90C27)

Cited In (14)

• 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
• 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
• On approximation of max-vertex-cover
• An Approximation Algorithm Based on Chain Implication for Constrained Minimum Vertex Covers in Bipartite Graphs
• Maximum weighted independent sets with a budget
• On Partial Vertex Cover and Budgeted Maximum Coverage Problems in Bipartite Graphs
• The maximum vertex coverage problem on bipartite graphs
• Simplicial complexes and closure systems induced by indistinguishability relations
• Indiscernibility structures induced from function sets : Graph and digraph case
• Parameterized Algorithms for Partial Vertex Covers in Bipartite Graphs
• A 0.821-ratio purely combinatorial algorithm for maximum \(k\)-vertex cover in bipartite graphs

This page was built for publication: Improved approximation of maximum vertex coverage problem on bipartite graphs

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