Abstract
We study the following NP-hard graph augmentation problem: Given a weighted graph G and a connected spanning subgraph H of G, find a minimum weight set of edges of G to be added to H so that H becomes 2-edge-connected. We provide a formulation of the problem as a set covering problem, and we analyze the conditions for which the linear programming relaxation of our formulation always gives an integer solution. This yields instances of the problem that can be solved in polynomial time. As we will show in the paper, these particular instances have not only theoretical but also practical interest, since they model a wide range of survivability problems in communication networks.
This work has been partially supported by the Research Project GRID.IT, funded by the Italian Ministry of Education, University and Research, and by the CNR-Agenzia 2000 Program, under Grant No. CNRC00CAB8.
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
Eswaran, K.P., Tarjan, R.E.: Augmentation problems. SIAM Journal on Computing 5(4), 653–665 (1976)
Even, G., Feldman, J., Kortsarz, G., Nutov, Z.: A 3/2-approximation algorithm for augmenting the edge-connectivity of a graph from 1 to 2 using a subset of a given edge set. In: Goemans, M.X., Jansen, K., Rolim, J.D.P., Trevisan, L. (eds.) RANDOM 2001 and APPROX 2001. LNCS, vol. 2129, pp. 90–101. Springer, Heidelberg (2001)
Frank, A.: Augmenting graphs to meet edge-connectivity requirements. SIAM Journal on Discrete Mathematics 5(1), 25–53 (1992)
Frederickson, G.N., Jájá, J.: Approximation algorithm for several graph augmentation problems. SIAM Journal on Computing 10(2), 270–283 (1981)
Gabow, H.N.: Application of a poset representation to edge-connectivity and graph rigidity. In: Proc. 32nd Ann. IEEE Symp. on Foundations of Computer Science (FOCS 1991), pp. 812–821. IEEE Computer Society, Los Alamitos (1991)
Galluccio, A., Proietti, G.: Polynomial time algorithms for edge-connectivity augmentation problems. Algorithmica 36(4), 361–374 (2003)
Hochbaum, D.S.: Approximating covering and packing problems: set cover, vertex cover, independent set and related problems. In: Hochbaum, D.S. (ed.) Approximation Algorithms for NPHard Problems. PWS Publishing Company, Boston (1996)
Hochbaum, D.S., Megiddo, N., Naor, J.S., Tamir, A.: Tight bounds and 2- approximation algorithms for integer programs with two variables per inequality. Mathematical Programming 62, 69–83 (1993)
Hoffman, A.J., Kruskal, J.B.: Integral boundary points of convex polyhedra. In: Kuhn, H.W., Tucker, A.W. (eds.) Linear Inequalities and Related Systems, pp. 223–246. Princeton University Press, New Jersey (1956)
Khuller, S., Thurimella, R.: Approximation algorithms for graph augmentation. Journal of Algorithms 14(2), 214–225 (1993)
Khuller, S.: Approximation algorithms for finding highly connected subgraphs. In: Hochbaum, D.S. (ed.) Approximation Algorithms for NP-Hard Problems. PWS Publishing Company, Boston (1996)
Nagamochi, H.: An approximation for finding a smallest 2-edge-connected subgraph containing a specified spanning tree. Discrete Applied Mathematics 126(1), 83–113 (2003)
Nemhauser, G.L., Wolsey, L.A.: Integer and Combinatorial Optimization. J. Wiley & Sons, Chichester (1986)
Schrijver, A.: Theory of Linear and Integer Programming. J. Wiley & Sons, Chichester (1986)
Watanabe, T., Nakamura, A.: Edge-connectivity augmentation problems. Journal of Computer and System Sciences 35(1), 96–144 (1987)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2004 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Conforti, M., Galluccio, A., Proietti, G. (2004). Edge-Connectivity Augmentation and Network Matrices. In: Hromkovič, J., Nagl, M., Westfechtel, B. (eds) Graph-Theoretic Concepts in Computer Science. WG 2004. Lecture Notes in Computer Science, vol 3353. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-30559-0_30
Download citation
DOI: https://doi.org/10.1007/978-3-540-30559-0_30
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-24132-4
Online ISBN: 978-3-540-30559-0
eBook Packages: Computer ScienceComputer Science (R0)