Improved Approximation Algorithms for Weighted 2- and 3-Vertex Connectivity Augmentation Problems.

Michal Penn Haya Shasha-Krupnik

Published in: J. Algorithms (1997)

Keyphrases

approximation algorithms
vertex cover
np hardness
np hard
approximation schemes
exact algorithms
special case
worst case
undirected graph
minimum cost
randomized algorithms
network design problem
set cover
facility location problem
primal dual
objective function
constant factor