Crown reductions for the Minimum Weighted Vertex Cover problem

Miroslav Chlebík Janka Chlebíková

Published in: Electron. Colloquium Comput. Complex. (2004)

Keyphrases

vertex cover
approximation algorithms
precedence constraints
planar graphs
minimum cost
partial order
constant factor
optimality criterion
special case
scheduling problem
np hard
worst case
information theoretic
branch and bound algorithm
spanning tree
polynomial time approximation