Name
Abstract | ||
|---|---|---|
The vertex cover problem is a classic NP-complete problem for which the best worst-case approximation ratio is roughly 2. In this paper, we use a collection of simple reductions, each of which guarantees an approximation ratio of $\frac{3}{2}$, to find approximate vertex covers for a large collection of test graphs from various sources. We explain these reductions and explore the interaction between them. These 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 every single graph in our large collection of test examples. |
Year | DOI | Venue |
|---|---|---|
2005 | 10.1007/11427186_47 | WEA |
Keywords | Field | DocType |
worst-case approximation ratio,approximation ratio,vertex cover,approximate vertex,test graph,vertex cover problem,test example,2-approximate vertex cover,large collection,classic np-complete problem,col,weed management,np complete problem | Discrete mathematics,Approximation algorithm,Graph,Combinatorics,Algorithmics,Vertex (geometry),Edge cover,Vertex cover,Linear programming relaxation,Mathematics,Feedback vertex set | Conference |
Volume | ISSN | ISBN |
3503 | 0302-9743 | 3-540-25920-1 |
Citations | PageRank | References |
7 | 0.53 | 14 |
Authors | ||
2 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Eyjolfur Asgeirsson | 1 | 7 | 0.53 |
| C Stein | 2 | 1207 | 125.21 |