A list heuristic for vertex cover (2008)
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 + 3/2 for...
Approximated Vertex Cover for Graphs with Perfect Matchings (2006)
IMAMURA, Tomokazu, IWAMA, Kazuo, TSUKIJI, Tatsuie
Chen and Kanj considered the VERTEX COVER problem for graphs with perfect matchings (VC-PM). They showed that: (i) There is a reduction from general VERTEX COVER to VC-PM, which guarantees that if...