Special edges, and approximating the smallest directed k-edge connected spanning subgraph
Harold N. Gabow · 2004
We give two approximation algorithms for finding the smallest k-edge connected spanning subgraph of a digraph. For multidigraphs we achieve performance ratio 2 - 1/3k. This is the first known ratio strictly less than 2. For simple digraphs the best known approximation algorithm is due to Cheriyan and Thurimella. We improve their analysis of the number of of a simple digraph. This improves the performance ratio of their algorithm for simple digraphs from 1 + 4/√k to slightly more than 1 + √2/k, for k ≥ 15. Our analysis of the number of special edges is tight for k ≥ 15. For 5