Given an undirected, 2-edge-connected, and real weighted graph G, with n vertices and m edges, and given a spanning tree T of G, the 2-edge-connectivity augmentation problem with respect to G and T consists of finding a minimum-weight set of edges of G whose addition to T makes it 2-edge-connected. While the general problem is NP-hard, in this paper we prove that it becomes polynomial time solvable if T can be rooted in such a way that a prescribed topological condition with respect to G is satisfied. In such a case, we provide an O(n(m+h+δ3)) time algorithm for solving the problem, where h and δ are the height and the maximum degree of T, respectively. A faster version of our algorithm can be used for 2-edge connecting a spider tree, that is a tree with at most one vertex of degree greater than two. This finds application in strengthening the reliability of optical networks.
Augmenting the Edge-Connectivity of a Spider Tree / Bilò, Davide; Proietti, Guido. - 3341:(2004), pp. 159-171. (Intervento presentato al convegno 15th International Symposium on Algorithms and Computation (ISAAC).) [10.1007/978-3-540-30551-4_16].
Augmenting the Edge-Connectivity of a Spider Tree
BILÒ, Davide;
2004-01-01
Abstract
Given an undirected, 2-edge-connected, and real weighted graph G, with n vertices and m edges, and given a spanning tree T of G, the 2-edge-connectivity augmentation problem with respect to G and T consists of finding a minimum-weight set of edges of G whose addition to T makes it 2-edge-connected. While the general problem is NP-hard, in this paper we prove that it becomes polynomial time solvable if T can be rooted in such a way that a prescribed topological condition with respect to G is satisfied. In such a case, we provide an O(n(m+h+δ3)) time algorithm for solving the problem, where h and δ are the height and the maximum degree of T, respectively. A faster version of our algorithm can be used for 2-edge connecting a spider tree, that is a tree with at most one vertex of degree greater than two. This finds application in strengthening the reliability of optical networks.I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
