Abstract
Algorithms for Single Link Failure Recovery and Related Problems
by: Amit M. Bhosle and Teofilo F. Gonzalez
Abstract:
We investigate the single link failure recovery problemand its application to the alternate path routing problem for ATMnetworks, and the $k$-replacement edges for each edge of a minimumcost spanning tree. Specifically, given a 2-connected graph $G$,a specified node $s$, and a shortest paths tree $\\mathcal{T}_s =\\{ e_1,$ $e_2,$ $\\ldots$, $e_{n-1} \\}$ of $s$, where $e_i = (x_i,y_i)$and $x_i=parent_{\\mathcal{T}_s}(y_i)$, find a shortest pathfrom $y_i$ to $s$ in the graph $G\\backslash e_i$ for$1\\leq i\\leq n-1$. We present an $O(m+n\\log n)$ time algorithm forthis problem and a linear time algorithm for the case when allweights are equal. When the edge weights are integers, we presentan algorithm that takes $O(m+T_{sort}(n))$ time, where $T_{sort}(n)$is the time required to sort $n$ integers. We establish a lowerbound of $\\Omega(min(m\\sqrt{n},n^2))$ for the directed version ofour problem under the path comparison model. We show that anysolution to the single link recovery problem can be adapted to solvethe alternate path routing problem in ATM networks. Our techniqueto solve the single link failure recovery problem is adapted tofind the $k$-replacement edges for the tree edges of a minimumcost spanning tree in $O(m + n \\log n)$ time
Keywords:
Single Link Failure Recovery, ATM Networks, Efficient Algorithms, Alternate Path Routing, MST k-replacement edges, MST k most vital edges.
Date:
October 2003
Document: 2003-35
