An Ear Decomposition Approach to Approximating the Smallest 3-Edge Connected Spanning Subgraph of a Multigraph
Author:
- Harold N. GabowHGHarold N. Gabow
- 1 January 2004
- journal article
- Published by Society for Industrial & Applied Mathematics (SIAM) in SIAM Journal on Discrete Mathematics
- Vol. 18 (1) , 41-70
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 [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) )$.
Keywords
This publication has 6 references indexed in Scilit:
- Improving on the 1.5-Approximation of a Smallest 2-Edge Connected Spanning SubgraphSIAM Journal on Discrete Mathematics, 2001
- Factor 4/3 Approximations for Minimum 2-Connected Subgraphs2000
- Approximating Minimum-Size k-Connected Spanning Subgraphs via MatchingSIAM Journal on Computing, 2000
- A Better Approximation Ratio for the Minimum Sizek-Edge-Connected Spanning Subgraph ProblemJournal of Algorithms, 1998
- Improved Approximation Algorithms for Uniform Connectivity ProblemsJournal of Algorithms, 1996
- Biconnectivity approximations and graph carvingsJournal of the ACM, 1994