Approximation algorithms for the maximum vertex coverage problem on bounded degree graphs

DOI10.1016/J.TCS.2021.07.015MaRDI QIDQ820559zbMATH OpenOpenAlexFDO

Authors Peiyan Zhou, Haitao Jiang, Daming Zhu, Binhai Zhu

Publication date 27 September 2021

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.tcs.2021.07.015

zbMATH Keywords

approximationcubic graphmaximum vertex coverage

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Recommendations

• Improved approximation of maximum vertex coverage problem on bipartite graphs
• On approximation of max-vertex-cover
• On approximation of the vertex cover problem in hypergraphs
• Publication:4952635
• Improved Approximation Algorithms for the Vertex Cover Problem in Graphs and Hypergraphs

Cites work

• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 1342117 (Why is no real title available?)
• scientific article; zbMATH DE number 1445320 (Why is no real title available?)
• Approximating low-dimensional coverage problems
• Improved approximation of maximum vertex coverage problem on bipartite graphs
• Minconvex Factors of Prescribed Size in Graphs
• On Partial Vertex Cover and Budgeted Maximum Coverage Problems in Bipartite Graphs
• On approximation properties of the Independent set problem for degree 3 graphs
• On approximation properties of the independent set problem for low degree graphs
• Purely combinatorial approximation algorithms for maximum \(k\)-vertex cover in bipartite graphs
• Reducibility among combinatorial problems
• The budgeted maximum coverage problem
• The complexity of theorem-proving procedures
• The hardness of approximation: Gap location
• The importance of being biased
• The maximum vertex coverage problem on bipartite graphs

Cited in

(5)

• Improved approximation of maximum vertex coverage problem on bipartite graphs
• On approximation of max-vertex-cover
• Approximation Algorithms for Edge-Covering Problem
• On Partial Vertex Cover and Budgeted Maximum Coverage Problems in Bipartite Graphs
• Approximation algorithm for sweep coverage on graph

This page was built for publication: Approximation algorithms for the maximum vertex coverage problem on bounded degree graphs

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