Vertex Cover in Conflict Graphs: Complexity and a Near Optimal Approximation.

Dongjing Miao Jianzhong Li Xianmin Liu Hong Gao

Published in: COCOA (2015)

Keyphrases

vertex cover
approximation algorithms
worst case
planar graphs
polynomial time approximation
undirected graph
approximation ratio
np hard
computational complexity
special case
approximation guarantees
constant factor
precedence constraints
partial order
space complexity
error bounds
search algorithm