| A list heuristic for vertex cover (2008) | |||||||||||||||||
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 + 3/2 for a nonincreasing degree sequence, and show that no ordering can achieve an approximation ratio of less than √ ∆/2. | |||||||||||||||||
Publication details | |||||||||||||||||
| |||||||||||||||||