An Ear Decomposition Approach to Approximating the Smallest 3-Edge Connected Spanning Subgraph of a Multigraph
Harold N. Gabow · SIAM Journal on Discrete Mathematics · 2004
This paper gives a 3/2 approximation algorithm for the smallest 3-edge connected spanning subgraph of an undirected multigraph. The previous best algorithm of Khuller and Raghavachari [J. Algorithms, 21 (1996), pp. 434--450] has approximation ratio $5/3$. The algorithm of Cheriyan and Thurimella [SIAM J. Comput., 30 (2000), pp. 528--560] achieves ratio 3/2 for simple graphs. Our approach, based on the close relationship between an ear decomposition of a 2-edge connected graph and 3-edge connected components, enables us to achieve running time $O( m \alpha(m,n) )$.