| Article ID | Journal | Published Year | Pages | File Type |
|---|---|---|---|---|
| 1143176 | Operations Research Letters | 2007 | 4 Pages |
Abstract
We analyze a list heuristic for the vertex cover problem that handles the vertices in a given static order based on the degree sequence. We prove an approximation ratio of at most Δ/2+32 for a nonincreasing degree sequence, and show that no ordering can achieve an approximation ratio of less than Δ/2.
Keywords
Related Topics
Physical Sciences and Engineering
Mathematics
Discrete Mathematics and Combinatorics
Authors
David Avis, Tomokazu Imamura,