Abstract
Consider a complete graph G with the edge weights satisfying the β-sharpened triangle inequality: weight(u,v) ≤ β (weight(u,x) + weight(x,v) ), for 1/2 ≤ β < 1. We study the NP-hard problem of finding a minimum weight spanning subgraph of G which is k-vertex-connected, k≥ 2, and give a detailed analysis of an approximation quadratic-time algorithm whose performance ratio is \(\frac{\beta}{1 - \beta}\).
The algorithm is derived from the one presented by Böckenhauer et al. in [3] for the k-edge connectivity problem on graphs satisfying the β-sharpened triangle inequality.
Work partially supported by funds for the research from MIUR, grant ex-60% 2002 Università di Salerno.
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
Auletta, V., Dinitz, Y., Nutov, Z., Parente, M.: A 2 Approximation Algorithms for Finding an Optimum 3 Vertex Connected Spanning Subgraph. J. of Algorithms 32, 21–30 (1999)
Böckenauer, H.-J., Bongartz, D., Hromkovič, J., Klasing, R., Proietti, G., Seibert, S., Unger, W.: On the hardness of constructing minimal 2-connected spanning subgraphs in complete graphs with sharpened triangle inequality. In: Agrawal, M., Seth, A.K. (eds.) FSTTCS 2002. LNCS, vol. 2556, pp. 59–70. Springer, Heidelberg (2002)
Böckenauer, H.-J., Bongartz, D., Hromkovič, J., Klasing, R., Proietti, G., Seibert, S., Unger, W.: On k-Edge-Connectivity Problems with Sharpened Triangle Inequality. To appear in Proc. of CIAC 2003. LNCS series (2003)
Böckenauer, H.-J., Hromkovič, J., Klasing, R., Seibert, S., Unger, W.: Approximation Algorithms for the TSP with Sharpened Triangle Inequality. Information Processing Letters 75, 133–138 (2000)
Böckenauer, H.-J., Hromkovič, J., Klasing, R., Seibert, S., Unger, W.: An Improved Lower Bound on the Approximability Algorithms for the TSP with Sharpened Triangle Inequality. In: Reichel, H., Tison, S. (eds.) STACS 2000. LNCS, vol. 1770, pp. 382–394. Springer, Heidelberg (2000)
Czumaj, A., Lingas, A.: On Approximability of the minimum-cost k-connected spanning subgraph problem. In: Proc. of SODA 1999, pp. 281–290 (1999)
Fernandes, C.G.: A Better Approximation Ratio for the Minimum Size k-Edge- Connected Spanning Subgraph Problem. J. of Algorithms 28(1), 105–124 (1998)
Garey, M.R., Johnson, D.S.: Computers and Intractability. W.H. Freeman and Company, New York (1979)
Khuller, S., Vishkin, U.: Biconnectivity approximation and graph carvings. Journal of the ACM 41, 214–235 (1994)
Penn, M., Shasha-Krupnik, H.: Improved approximation Algorithms for weighted 2 and 3-vertex connectivity augmentation. J. of Algorithms 22, 187–196 (1997)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2003 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Ferrante, A., Parente, M. (2003). An Approximation Algorithm for the Minimum Weight Vertex-Connectivity Problem in Complete Graphs with Sharpened Triangle Inequality. In: Blundo, C., Laneve, C. (eds) Theoretical Computer Science. ICTCS 2003. Lecture Notes in Computer Science, vol 2841. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-45208-9_12
Download citation
DOI: https://doi.org/10.1007/978-3-540-45208-9_12
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-20216-5
Online ISBN: 978-3-540-45208-9
eBook Packages: Springer Book Archive