Better performance bounds for finding the smallest k-edge connected spanning subgraph of a multigraph
Harold N. Gabow · 2003
Khuller and Raghavachari [12] present an approximation algorithm (the KR algorithm) for finding the smallest k-edge connected spanning subgraph (k-ECSS) of an undirected multigraph. They prove the KR algorithm has approximation ratio