A Faster Computation of All the Best Swap Edges of a Tree Spanner

Given a 2-edge connected, positively real-weighted graph

G

with

n

vertices and

m

edges, a

tree σ-spanner

of

G

is a spanning tree

T

in which for every pair of vertices, the ratio of their distance in

T

over that in

G

is bounded by

σ

, the so-called

stretch factor

of

T

. Tree spanners with provably good stretch factors find applications in communication networks, distributed systems, and network design, but unfortunately –as any tree-based infrastructure– they are highly sensitive to even a single link failure, since this results in a network disconnection. Thus, when such an event occurs, the overall effort that has to be afforded to rebuild an effective tree spanner (i.e., computational costs, set-up of new links, updating of the routing tables, etc.) can be prohibitive. However, if the edge failure is only

transient

, these costs can simply be avoided, by promptly reestablishing the connectivity through a careful selection of a temporary

swap edge

, i.e., an edge in

G

reconnecting the two subtrees of

T

induced by the edge failure. According to the tree spanner’s nature, a

best swap edge

for a failing edge

e

is then a swap edge generating a reconnected tree of minimum stretch factor w.r.t. distances in the graph

G

deprived of edge

e

. For this problem we provide two efficient linear-space solutions for both the weighted and the unweighted case, running in

O

(

m

2

log

α

(

m

,

n

)) and

O

(

mn

log

n

) time, respectively. As discussed in the paper, our algorithms also improve on the time complexity of previous results provided for other related settings of the problem.