  A tree $\sigma$-spanner of a positively real-weighted $n$-vertex and $m$-edge
undirected graph $G$ is a spanning tree $T$ of $G$ which approximately
preserves (i.e., up to a multiplicative stretch factor $\sigma$) distances in
$G$. Tree spanners with provably good stretch factors find applications in
communication networks, distributed systems, and network design. However,
finding an optimal or even a good tree spanner is a very hard computational
task. Thus, if one has to face a transient edge failure in $T$, the overall
effort that has to be afforded to rebuild a new tree spanner (i.e.,
computational costs, set-up of new links, updating of the routing tables, etc.)
can be rather prohibitive. To circumvent this drawback, an effective
alternative is that of associating with each tree edge a best possible (in
terms of resulting stretch) swap edge -- a well-established approach in the
literature for several other tree topologies. Correspondingly, the problem of
computing all the best swap edges of a tree spanner is a challenging
algorithmic problem, since solving it efficiently means to exploit the
structure of shortest paths not only in $G$, but also in all the scenarios in
which an edge of $T$ has failed. For this problem we provide a very efficient
solution, running in $O(n^2 \log^4 n)$ time, which drastically improves (almost
by a quadratic factor in $n$ in dense graphs!) on the previous known best
result.
