Algorithms for Single Link Failure Recovery and Related Problems - Bhosle, Amit; Gonzalez, Teofilo (Journal of Graph Algorithms and Applications, 2004)
We investigate the single link failure recoveryproblem and its application tothe alternate path routing problem for ATM networks, and the k-replacement edgesfor each edge of a minimum cost spanning tree.Specifically, given a 2-connectedgraph G, a specified node s, and a shortest paths treeTs = { e1, e2, …, en−1 } of s, where ei = (xi,yi)and xi=parentTs(yi), find a shortest pathfrom yi to s in the graph G\ei for 1 ≤ i ≤ n−1. We presentan O(m+nlogn) time algorithm for this problem and a lineartime algorithm for thecase when all weights are equal. When the edge weights are integers,we present an algorithm that takes O(m+Tsort(n)) time, whereTsort(n) isthe time required to sort n integers.We establish a lower bound of Ω(min(m√n,n2)) for thedirected version of our problemunder the path comparison model, where Ts is the shortest pathsdestination tree of s.We show that any solution to thesingle link recovery problem can be adapted to solve the alternate path routingproblem in ATM networks.Our technique for the single link failure recovery problem isadapted tofind the k-replacement edges for the tree edges of a minimum cost spanning tree inO(m + n logn) time. <!---->