Abstract
We present factor \( \tfrac{4} {3} \) approximation algorithms for the problems of finding theminimum 2-edge connected and theminimum 2-vertex connected spanning subgraph of a given undirected graph.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
References
Carr, R., Ravi, R.: A new bound for the 2-edge connected subgraph problem. Proc 6th Annual International IPCO (1998)
Cheriyan, J., Sebö, A., Sigeti, Z.: Improving on the 1.5-approximation of a smallest 2-edge connected spanning subgraph. Proc 6th Annual International IPCO (1998)
N. Garg, A. Singla, S. Vempala, Improved approximations for biconnected subgraphs via better lower bounding techniques. Proc 6th Annual SODA (1993)
M. Grötschel, L. Lovász and A. Schrijver, Geometric algorithms and combinatorial optimization. Springer-Verlag, New York (1988)
D. Hartvigsen, Extensions of Matching Theory. Ph.D. thesis, GSIA, Carnegie Mellon University (1984)
S. Khuller and U. Vishkin, Biconnectivity approximations and graph carvings. Journal of the ACM 41 (1994) 214–35
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2000 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Vempala, S., Vetta, A. (2000). Factor 4/3 Approximations for Minimum 2-Connected Subgraphs. In: Jansen, K., Khuller, S. (eds) Approximation Algorithms for Combinatorial Optimization. APPROX 2000. Lecture Notes in Computer Science, vol 1913. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-44436-X_26
Download citation
DOI: https://doi.org/10.1007/3-540-44436-X_26
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-67996-7
Online ISBN: 978-3-540-44436-7
eBook Packages: Springer Book Archive