Polynomial Time Algorithms for 2-Edge-Connectivity Augmentation Problems |
| |
Authors: | Galluccio and Proietti |
| |
Affiliation: | (1) Istituto di Analisi dei Sistemi ed Informatica, CNR, Viale Manzoni 30, 00185 Roma, Italy. gallucci@iasi.rm.cnr.it., IT;(2) Dipartimento di Informatica, Università di L'Aquila, Via Vetoio, 67010 L'Aquila, Italy, proietti@di.univaq.it, and Istituto di Analisi dei Sistemi ed Informatica, CNR, Viale Manzoni 30, 00185 Roma, Italy., IT |
| |
Abstract: | Abstract. Given a 2-edge-connected, real weighted graph G with n vertices and m edges, the 2-edge-connectivity augmentation problem is that of finding a minimum weight set of edges of G to be added to a spanning subgraph H of G to make it 2-edge-connected. While the general problem is NP-hard and 2 -approximable, in this paper we prove that it becomes polynomial time solvable if H is a depth-first search tree of G . More precisely, we provide an efficient algorithm for solving this special case which runs in O
(M · α(M,n)) time, where α is the classic inverse of Ackermann's function and M=m · α(m,n) . This algorithm has two main consequences: first, it provides a faster 2 -approximation algorithm for the general 2 -edge-connectivity augmentation problem; second, it solves in O
(m · α(m,n)) time the problem of restoring, by means of a minimum weight set of replacement edges, the 2 -edge-connectivity of a 2-edge-connected communication network undergoing a link failure. |
| |
Keywords: | , Augmentation problems, Graph algorithms, Data structures, Network survivability, |
本文献已被 SpringerLink 等数据库收录! |
|