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

ABSTRACT

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 [8] has approximation ratio 5/3. The algorithm of Cheriyan and Thurimella [3] achieves ratio 3/2 for simple graphs. Our approach is based on the relationship between an ear decomposition of a 2-edge connected graph and 3-edge connected components, enabling us to achieve running time O(mα(m,n)).

REFERENCES

• 1: Thomas T. Cormen , Charles E. Leiserson , Ronald L. Rivest, Introduction to algorithms, MIT Press, Cambridge, MA, 1990
• 2: J. Cheriyan , A. Sebo , Z. Szigeti, Improving on the 1.5-Approximation of a Smallest 2-Edge Connected Spanning Subgraph, SIAM Journal on Discrete Mathematics, v.14 n.2, p.170-180, 2001 [doi>10.1137/S0895480199362071]
• 3: Joseph Cheriyan , Ramakrishna Thurimella, Approximating Minimum-Size k-Connected Spanning Subgraphs via Matching, SIAM Journal on Computing, v.30 n.2, p.528-560, 2000 [doi>10.1137/S009753979833920X]
• 4: Cristina G. Fernandes, A better approximation ratio for the minimum size k-edge-connected spanning subgraph problem, Journal of Algorithms, v.28 n.1, p.105-124, July 1, 1998 [doi>10.1006/jagm.1998.0931]
• 5: H. N. Gabow, An ear decomposition approach to approximating the smallest 3-edge connected spanning subgraph of a multigraph, available at http://www.cs.colorado.edu/~hal.
• 6: Naveen Garg , Vempala S. Santosh , Aman Singla, Improved approximation algorithms for biconnected subgraphs via better lower bounding techniques, Proceedings of the fourth annual ACM-SIAM Symposium on Discrete algorithms, p.103-111, January 25-27, 1993, Austin, Texas, United States
• 7: Samir Khuller, Approximation algorithms for finding highly connected subgraphs, Approximation algorithms for NP-hard problems, PWS Publishing Co., Boston, MA, 1996
• 8: Samir Khuller , Balaji Raghavachari, Improved approximation algorithms for uniform connectivity problems, Journal of Algorithms, v.21 n.2, p.434-450, Sept. 1996 [doi>10.1006/jagm.1996.0052]
• 9: Samir Khuller , Uzi Vishkin, Biconnectivity approximations and graph carvings, Journal of the ACM (JACM), v.41 n.2, p.214-235, March 1994 [doi>10.1145/174652.174654]
• 10: Santosh Vempala , Adrian Vetta, Factor 4/3 approximations for minimum 2-connected subgraphs, Proceedings of the Third International Workshop on Approximation Algorithms for Combinatorial Optimization, p.262-273, September 05-08, 2000
• 11: D. B. West, Introduction to Graph Theory, 2nd Ed., Prentice-Hall, 2001.