Home  Issues  About JGAA  Instructions for Authors 
DOI: 10.7155/jgaa.00092
Algorithms for Single Link Failure Recovery and Related Problems
Vol. 8, no. 3, pp. 275294, 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 kreplacement edges
for each edge of a minimum cost spanning tree.
Specifically, given a 2connected
graph G, a specified node s, and a shortest paths tree
T_{s} = { e_{1}, e_{2}, …, e_{n−1} } 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 G\e_{i} 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+T_{sort}(n)) time, where
T_{sort}(n) is
the time required to sort n integers.
We establish a lower bound of Ω(min(m√n,n^{2})) for the
directed version of our problem
under the path comparison model, where 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 kreplacement edges for the tree edges of a minimum cost spanning tree in
O(m + n logn) time.

Journal Supporters
