Improved Approximation Algorithms for the Vertex Cover Problem in Graphs and Hypergraphs.

Published in: SIAM J. Comput. (2002)

Keyphrases

vertex cover
approximation algorithms
undirected graph
planar graphs
np hard
special case
graph theory
minimum cost
worst case
precedence constraints
constant factor
approximation guarantees
primal dual
approximation ratio
polynomial time approximation
directed graph
simulated annealing
upper bound
lower bound