On the Approximability of the Vertex Cover and Related Problems.

Qiaoming Han Abraham P. Punnen

Published in: AAIM (2010)

Keyphrases

related problems
vertex cover
approximation algorithms
polynomial time approximation
np hard
special case
worst case
minimum cost
constant factor
precedence constraints
undirected graph
approximation ratio
planar graphs
search algorithm
partial order