Vertex cover in graphs with locally few colors.

Fabian Kuhn Monaldo Mastrolilli

Published in: Inf. Comput. (2013)

Keyphrases

vertex cover
planar graphs
approximation algorithms
partial order
precedence constraints
weighted graph
maximum likelihood
minimum cost
undirected graph
np hard
bipartite graph
spanning tree
approximation ratio
minimum weight
optimality criterion
polynomial time approximation