Amazon Development Center India

Thursday, November 04, 2004

Research Pubs from Amazon India

Algorithms for Single Link Failure Recovery

and Related Problems

Amit M Bhosle, Teofilo F Gonzalez
Journal of Graph Algorithms & Applications (to appear)

We investigate the single link failure recovery
problems which deal with rerouting issues in networks
prone to link failure. Furthermore, the knowledge
of the link failure is not propagated across the
network, and the failure is discovered only when one
is about to use the failed link. We present near
optimal algorithms for arbitrarily weighted undirected
graphs, and achive an improved algorithm for
unweighted (undirected) graphs, and integer-edge-
weighted (undirected) graphs. For directed graphs,
we present a super-linear lower bound for the problem.
Finally, we extend our techniques to devise a near-optimal
algorithm for the k minimum weight replacement edges for
the tree edges of a minimum-spanning-tree.
[PDF] [Bibtex]