Algorithms for single link failure recovery and related problems.

*(English)*Zbl 1085.05057Summary: We investigate the single link failure recovery problem and its application to the alternate path routing problem for ATM networks, and the \(k\)-replacement edges for each edge of a minimum cost 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,\dots, e_{n-1}\}\) of \(s\), where \(e_i=(x_i,y_i)\) and \(x_i= \text{parent}_{T_{s}} (y_i)\), find a shortest path from \(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 for this problem and a linear time algorithm for the case when all weights are equal. When the edge weights are integers, we present an algorithm that takes \(O(m + T_{\text{sort}}(n))\) time, where \(T_{\text{sort}}(n)\) is the time required to sort \(n\) integers. We establish a lower bound of \(\Omega(\min(m\sqrt n, n^2))\) for the directed version of our problem under the path comparison model, where \({\mathcal T}_s\) is the shortest paths destination tree of \(s\). We show that any solution to the single link recovery problem can be adapted to solve the alternate path routing problem in ATM networks. Our technique for the single link failure recovery problem is adapted to find the \(k\)-replacement edges for the tree edges of a minimum cost spanning tree in \(O(m + n \log n)\) time.