Abstract. Let G=(V,E) be a 2-edge connected, undirected and nonnegatively weighted graph, and let S(r) be a single source shortest paths tree (SPT) of G rooted at r ∈ V . Whenever an edge e in S(r) fails, we are interested in reconnecting the nodes now disconnected from the root by means of a single edge e' crossing the cut created by the removal of e . Such an edge e' is named a swap edge for e . Let S e/e' (r) be the swap tree (no longer an SPT, in general) obtained by swapping e with e' , and let S e be the set of all possible swap trees with respect to e . Let F be a function defined over S e that expresses some feature of a swap tree, such as the average length of a path from the root r to all the nodes below edge e , or the maximum length, or one of many others. A best swap edge for e with respect to F is a swap edge f such that F(S e/f (r)) is minimum.
In this paper we present efficient algorithms for the problem of finding a best swap edge, for each edge e of S(r) , with respect to several objectives. Our work is motivated by a scenario in which individual connections in a communication network suffer transient failures. As a consequence of an edge failure, the shortest paths to all the nodes below the failed edge might completely change, and it might be desirable to avoid an expensive switch to a new SPT, because the failure is only temporary. As an aside, what we get is not even far from a new SPT: our analysis shows that the trees obtained from the swapping have features very similar to those of the corresponding SPTs rebuilt from scratch.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
Author information
Authors and Affiliations
Rights and permissions
About this article
Cite this article
Nardelli, ., Proietti, . & Widmayer, . Swapping a Failing Edge of a Single Source Shortest Paths Tree Is Good and Fast . Algorithmica 35, 56–74 (2003). https://doi.org/10.1007/s00453-002-0988-z
Issue Date:
DOI: https://doi.org/10.1007/s00453-002-0988-z