Improved Approximation Algorithms for Un
โ
Samir Khuller; Balaji Raghavachari
๐
Article
๐
1996
๐
Elsevier Science
๐
English
โ 174 KB
The problem of finding minimum-weight spanning subgraphs with a given connectivity requirement is considered. The problem is NP-hard when the connectivity requirement is greater than one. Polynomial time approximation algorithms for various weighted and unweighted connectivity problems are given. Th