Polynomial time algorithms for 2-edge-connectivity augmentation problems
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 . alpha(M, n)) time, where alpha is the classic inverse of Ackermann's function and M = m . alpha(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 0(m . alpha(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.
augmentation problems graph algorithms data structures network survivability