Finding Best Swap Edges Minimizing the Routing Cost of a Spanning Tree

Given ann-node, undirected and 2-edge-connected graphG=(V,E)with positive real weights on itsmedges, given a set ofksourcenodesS⊆V, and given a spanning treeTofG,therouting cost fromSofTis the sum of the distances in Tfrom every sources∈Sto all the other nodes of G. If an edge eofTundergoes atransient failure, and one needs to promptly reestablish the connectivity, then to reduce set-up and rerouting costs it makes sense to temporarily replaceeby means of aswap edge, i.e., an edge in Greconnecting the two subtrees of Tinduced by the removal of e. Then, a best swap edgeforeis a swap edge which minimizes the routing cost fromSof the tree obtained after the swapping. As a natural extension, theall-best swap edgesproblem is that of finding a best swap edge foreveryedge of T, and this has been recently solved in O(mn)time and linear space. In this paper, we focus our attention on the relevant cases in whichk=O(1)andk=n, which model realistic communication paradigms. For these cases, we improve the above result by presenting an O(m)time and linear space algorithm. Moreover, for the case k=n, we also provide an accurate analysis showing that the obtained swap tree is effective in terms of routing cost. Indeed, if the input treeThas a routing cost from Vwhich is a constant-factor away from that of aminimum routing-cost spanning tree (whose computation is a problem known to be inAPX), and if in addition nodes in Tenjoys a suitable distance stretching property from a tree centroid (which can be constructively induced, as we show), then the tree obtained after the swapping has a routing cost fromVwhich is still a constant-ratio approximation of that of a new (i.e., in the graph deprived of the failed edge) minimum routing-cost spanning tree.