Data di Pubblicazione:
2006
Abstract:
We provide a new LP relaxation of the maximum vertex cover problem and a
polynomial-time algorithm that finds a solution within the approximation
factor 1-1/(2\bar q),
where \bar q is the size of the smallest clique in a given
clique-partition of the edge weighting of G.
Tipologia CRIS:
01.01 Articolo in rivista
Keywords:
vertex cover; polyhedra; approximation algorithm
Elenco autori:
Nobili, Paolo; Galluccio, Anna
Link alla scheda completa:
Pubblicato in: