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

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$ \emph{source} nodes $S\subseteq V$, and given a spanning tree $T$ of $G$, the \emph{routing cost} of $T$ w.r.t. $S$ is the sum of the distances in $T$ from every source $s\in S$ to all the other nodes of $G$. If an edge $e$ of $T$ undergoes a \emph{transient} failure and connectivity needs to be promptly reestablished, then to reduce set-up and rerouting costs it makes sense to temporarily replace $e$ by means of a \emph{swap edge}, i.e., an edge in $G$ reconnecting the two subtrees of $T$ induced by the removal of $e$. Then, a \emph{best swap edge} for $e$ is a swap edge which minimizes the routing cost of the tree obtained after the swapping. As a natural extension, the \emph{all-best swap edges} problem is that of finding a best swap edge for \emph{every} edge of $T$. Such a problem has been recently solved in $O(mn)$ time and linear space for arbitrary $k$, and in $O(n^2+m\log n)$ time and $O(n^2$) space for the special case $k=2$. In this paper, we are interested to the prominent cases $k=O(1)$ and $k=n$, which model realistic communication paradigms. For these cases, we present a linear space and $\widetilde O(m)$ time algorithm, and thus we improve both the above running times (but for quite dense graphs in the case $k=2$, for which however it is noticeable we make use of only linear space). Moreover, we provide an accurate analysis showing that when $k=n$, the obtained swap tree is effective in terms of routing cost. \hide{Indeed, if the input tree $T$ has a routing cost which is a constant-factor away from that of a \emph{minimum routing-cost spanning tree} (MRCST) of $G$ (i.e., a spanning tree minimizing the routing cost w.r.t. $V$, whose computation is known to be \np-hard), 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 which is a constant-ratio approximation of the routing cost of a new (i.e., in the graph deprived of the failed edge) MRCST.}