Improved approximation of maximum vertex cover.

Anna Galluccio Paolo Nobili

Published in: Oper. Res. Lett. (2006)

Keyphrases

vertex cover
approximation algorithms
polynomial time approximation
approximation ratio
np hard
partial order
special case
planar graphs
worst case
minimum cost
constant factor
lower bound
error bounds
optimality criterion