Journal of Graph Algorithms and Applications
http://jgaa.info ISSN: 1526-1719
|
DOI: 10.7155/jgaa.00092 Algorithms for Single Link Failure Recovery and Related Problems Amit M. Bhosle and Teofilo F. Gonzalez Vol. 8, no. 3, pp. 275-294, 2004. Regular paper Abstract 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 Ts = { e1, e2, …, en−1 } of s, where ei = (xi,yi) and xi=parentTs(yi), find a shortest path from yi to s in the graph G\ei for 1 ≤ i ≤ n−1. We present an O(m+nlogn) 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+Tsort(n)) time, where Tsort(n) is the time required to sort n integers. We establish a lower bound of Ω(min(m√n,n2)) for the directed version of our problem under the path comparison model, where Ts 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 logn) time.
|
Revised: July 2004. Submitted: October 2003. Communicated by Balaji Raghavachari |
| Journal of Graph Algorithms and Applications |