Back to Search
Start Over
DIVIDE-AND-CONQUER APPROXIMATION ALGORITHM FOR VERTEX COVER.
- Source :
-
SIAM Journal on Discrete Mathematics . 2009, Vol. 23 Issue 3, p1261-1280. 20p. 2 Diagrams, 1 Chart, 5 Graphs. - Publication Year :
- 2009
-
Abstract
- The vertex cover problem is a classical NP–complete problem for which the best worstcase approximation ratio is 2–o(1). In this paper, we use a collection of simple graph transformations, each of which guarantees an approximation ratio of 3 2 , to find approximate vertex covers for a large collection of randomly generated graphs and test graphs from various sources. The graph reductions are extremely fast, and even though they by themselves are not guaranteed to find a vertex cover, we manage to find a 3 2 –approximate vertex cover for almost every single graph in our collection. The few graphs that we cannot solve have specific structure: they are triangle–free, with a minimum degree of at least 3, a lower bound of n 2 on the optimal vertex cover, and are unlikely to have a large bipartite subgraph. [ABSTRACT FROM AUTHOR]
Details
- Language :
- English
- ISSN :
- 08954801
- Volume :
- 23
- Issue :
- 3
- Database :
- Academic Search Index
- Journal :
- SIAM Journal on Discrete Mathematics
- Publication Type :
- Academic Journal
- Accession number :
- 51706860
- Full Text :
- https://doi.org/10.1137/070710275