An ear decomposition approach to approximating the smallest 3-edge connected spanning subgraph of a multigraph

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(malpha( m, n)).