Back to Search
Start Over
Approximation algorithms for the maximum vertex coverage problem on bounded degree graphs.
- Source :
-
Theoretical Computer Science . Oct2021, Vol. 888, p22-30. 9p. - Publication Year :
- 2021
-
Abstract
- The Maximum Vertex Coverage problem (abbreviated as MVC) is to maximum the number of edges covered by a set of vertices of size exactly K on a graph. This problem is the dual of the vertex cover problem and has attracted a lot of interests in the literature of approximation algorithm. So far, the best approximation factor for the MVC problem is 3/4, which is obtained using an LP-rounding method. The main results of this paper are new approximation algorithms for MVC on cubic graphs and 3-bounded graphs (the vertex degrees are at most 3). The approximation factor on cubic graphs is 79/90 (≈0.878), which is tight by analyzing the existence of a feasible solution for a linear programming system. This algorithm can also be extended to 3-bounded graphs and guarantees an approximation factor of 19/24 (≈0.792). [ABSTRACT FROM AUTHOR]
- Subjects :
- *APPROXIMATION algorithms
*LINEAR programming
*ALGORITHMS
*LINEAR systems
Subjects
Details
- Language :
- English
- ISSN :
- 03043975
- Volume :
- 888
- Database :
- Academic Search Index
- Journal :
- Theoretical Computer Science
- Publication Type :
- Academic Journal
- Accession number :
- 152576905
- Full Text :
- https://doi.org/10.1016/j.tcs.2021.07.015