Complexity and Approximation Results for the Connected Vertex Cover Problem.

Bruno Escoffier Laurent Gourvès Jérôme Monnot

Published in: WG (2007)

Keyphrases

vertex cover
approximation algorithms
worst case
polynomial time approximation
approximation ratio
computational complexity
np hard
special case
partial order
error bounds
planar graphs
closed form
space complexity
precedence constraints