Algorithms for Single Link Failure Recovery and Related Problems
Amit M. Bhosle, Teofilo F. Gonzalez · Journal of Graph Algorithms and Applications · 2004
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 T s = fe 1 ; e 2 ; : : : ; e n\\Gamma1 g of s, where e i = (x i ; y i ) and x i = parent Ts (y i ), find a shortest path from y i to s in the graph Gne i for 1 i n \\Gamma 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 sort (n)) time, where T sort (n) is the time required to sort n integers. We establish a lower bound of \\Omega\\Gamma min(m n; n )) for the directed version of our problem under the path comparison model.