A Better Approximation Ratio for the Min
✍
Cristina G Fernandes
📂
Article
📅
1998
🏛
Elsevier Science
🌐
English
⚖ 213 KB
Consider the minimum size k-edge-connected spanning subgraph problem: given a positive integer k and a k-edge-connected graph G, find a k-edge-connected spanning subgraph of G with the minimum number of edges. This problem is known to be NP-complete. Khuller and Raghavachari presented the first algo