Given a 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. Such a problem is well-known to be NP-hard, but it becomes solvable in polynomial time if $H$ is a depth-first search tree of $G$, and the fastest algorithm for this special case runs in $O(m+n \log n)$ time. In this paper, we sensibly improve such a bound, by providing an efficient algorithm running in $O(M \cdot \alpha(M,n))$ time, where $\alpha$ is the classic inverse of the Ackermann's function and $M=m \cdot \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 $O(m \cdot \alpha(m,n))$ time the problem of maintaining, by means of a minimum weight set of edges, the $2$-edge-connectivity of a 2-edge-connected communication network undergoing an edge failure, thus improving the previous $O(m+n \log n)$ time bound.
A Faster Approximation Algorithm for 2-Edge-Connectivity Augmentation
Galluccio A;Proietti G
2002
Abstract
Given a 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. Such a problem is well-known to be NP-hard, but it becomes solvable in polynomial time if $H$ is a depth-first search tree of $G$, and the fastest algorithm for this special case runs in $O(m+n \log n)$ time. In this paper, we sensibly improve such a bound, by providing an efficient algorithm running in $O(M \cdot \alpha(M,n))$ time, where $\alpha$ is the classic inverse of the Ackermann's function and $M=m \cdot \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 $O(m \cdot \alpha(m,n))$ time the problem of maintaining, by means of a minimum weight set of edges, the $2$-edge-connectivity of a 2-edge-connected communication network undergoing an edge failure, thus improving the previous $O(m+n \log n)$ time bound.I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
