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

DOI10.1016/J.TCS.2021.07.015OpenAlexW3184115741MaRDI QIDQ820559FDOQ820559

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

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

zbMATH Keywords

approximationcubic graphmaximum vertex coverage

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Cites Work

• Title not available (Why is that?)
• Reducibility among combinatorial problems
• The hardness of approximation: Gap location
• The maximum vertex coverage problem on bipartite graphs
• Minconvex Factors of Prescribed Size in Graphs
• The complexity of theorem-proving procedures
• The budgeted maximum coverage problem
• On approximation properties of the Independent set problem for degree 3 graphs
• The importance of being biased
• Title not available (Why is that?)
• On approximation properties of the independent set problem for low degree graphs
• Title not available (Why is that?)
• Purely combinatorial approximation algorithms for maximum \(k\)-vertex cover in bipartite graphs
• Approximating low-dimensional coverage problems
• Improved approximation of maximum vertex coverage problem on bipartite graphs
• On Partial Vertex Cover and Budgeted Maximum Coverage Problems in 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)