The Price of Connectivity for Vertex Cover: Perfect, Near-Perfect and Critical Graphs.

Eglantine Camby Jean Cardinal Samuel Fiorini Oliver Schaudt

Published in: CTW (2012)

Keyphrases

vertex cover
planar graphs
approximation algorithms
undirected graph
partial order
graph theory
special case
connected components
weighted graph
optimality criterion
pairwise
bipartite graph