A list heuristic for vertex cover

A list heuristic for vertex cover

0.00 Avg rating0 Votes
Article ID: iaor20081970
Country: Netherlands
Volume: 35
Issue: 2
Start Page Number: 201
End Page Number: 204
Publication Date: Mar 2007
Journal: Operations Research Letters
Authors: ,
Keywords: heuristics
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.

Reviews

Required fields are marked *. Your email address will not be published.