Crown reductions for the Minimum Weighted Vertex Cover problem.

Miroslav Chlebík Janka Chlebíková

Published in: Discret. Appl. Math. (2008)

Keyphrases

vertex cover
approximation algorithms
partial order
planar graphs
precedence constraints
minimum cost
constant factor
optimality criterion
search algorithm
np hard
dynamic programming
worst case
weighted graph
log likelihood
polynomial time approximation