Given an *n*-node, undirected and 2-edge-connected graph *G*=(*V*,*E*) with positive real weights on its *m* edges, given a set of *k**source* nodes *S*⊆*V*, and given a spanning tree *T* of *G*, the *routing cost from**S* of *T* is the sum of the distances in *T* from every source *s*∈*S* to all the other nodes of *G*. If an edge *e* of *T* undergoes a *transient* failure, and one needs to promptly reestablish the connectivity, then to reduce set-up and rerouting costs it makes sense to temporarily replace *e* by means of a *swap edge*, i.e., an edge in *G* reconnecting the two subtrees of *T* induced by the removal of *e*. Then, a *best swap edge* for *e* is a swap edge which minimizes the routing cost from *S* of the tree obtained after the swapping. As a natural extension, the *all-best swap edges* problem is that of finding a best swap edge for *every* edge 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 which *k*=*O*(1) and *k*=*n*, which model realistic communication paradigms. For these cases, we improve the above result by presenting an
$\widetilde{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 tree *T* has a routing cost from *V* which is a constant-factor away from that of a *minimum routing-cost spanning tree* (whose computation is a problem known to be in *APX*), and if in addition nodes in *T* enjoys 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 from *V* which 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.