Abstract
We give a \( \frac{{17}} {{12}} \) -approximation algorithm for the following NP- hard problem: Given a simple undirected graph, find a 2-edge connected span- ning subgraph that has the minimum number of edges. The best previous approximation guarantee was \( \frac{3} {2} \) . If the well known TSP \( \frac{4} {3} \) conjecture holds, then there is a \( \frac{4} {3} \) -approximation algorithm. Thus our main result gets half-way to this target.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
R. Carr and R. Ravi. A new bound for the 2-edge connected subgraph problem. In R. E. Bixby, E. A. Boyd, and R. Z. Ríos-Mercado, editors, Integer Programming and Combinatorial Optimization: Proceedings of the 6th International Conference on Integer Programming and Combinatorial Optimization, LNCS, Vol. 1412, pages 110–123. Springer, 1998. This volume.
J. Cheriyan and R. Thurimella. Approximating minimum-size k-connected spanning subgraphs via matching. Proc. 37th Annual IEEE Sympos. on Foundat. of Comput. Sci., pages 292–301, 1996.
N. Christofides. Worst-case analysis of a new heuristic for the traveling salesman problem. Technical report, G.S.I.A., Carnegie-Mellon Univ., Pittsburgh, PA, 1976.
A. Frank. Conservative weightings and ear-decompositions of graphs. Combinatorica, 13:65–81, 1993.
G. L. Frederickson and J. Ja’Ja’. On the relationship between the biconnectivity augmentation and traveling salesman problems. Theor. Comp. Sci., 19:189–201, 1982.
N. Garg, V. S. Santosh, and A. Singla. Improved approximation algorithms for biconnected subgraphs via better lower bounding techniques. Proc. 4th Annual ACM-SIAM Symposium on Discrete Algorithms, pages 103–111, 1993.
M. X. Goemans and D. J. Bertsimas. Survivable networks, linear programming relaxations and the parsimonious property. Mathematical Programming, 60:143–166, 1993.
S. Khuller and U. Vishkin. Biconnectivity approximations and graph carvings. Journal of the ACM, 41:214–235, 1994. Preliminary version in Proc. 24th Annual ACM STOC, pages 759–770, 1992.
L. Lovász. A note on factor-critical graphs. Studia Sci. Math. Hungar., 7:279–280, 1972.
L. Lovász and M. D. Plummer. Matching Theory. Akadémiai Kiadó, Budapest, 1986.
C. L. Monma, B. S. Munson, and W. R. Pulleyblank. Minimum-weight two-connected spanning networks. Mathematical Programming, 46:153–171, 1990.
H. Whitney. Nonseparable and planar graphs. Trans. Amer. Math. Soc., 34:339–362, 1932.
L. A. Wolsey. Heuristic analysis, linear programming and branch and bound. Mathematical Programming Study, 13:121–134, 1980
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 1998 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Cheriyan, J., Sebő, A., Szigeti, Z. (1998). An Improved Approximation Algorithm for Minimum Size 2-Edge Connected Spanning Subgraphs. In: Bixby, R.E., Boyd, E.A., Ríos-Mercado, R.Z. (eds) Integer Programming and Combinatorial Optimization. IPCO 1998. Lecture Notes in Computer Science, vol 1412. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-69346-7_10
Download citation
DOI: https://doi.org/10.1007/3-540-69346-7_10
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-64590-0
Online ISBN: 978-3-540-69346-8
eBook Packages: Springer Book Archive