A tree σ-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 σ) 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. Keywords and phrases Transient edge failure, Swap algorithm, Tree spanner The problem of computing all the best swap edges (ABSE) of a tree has a long and rich algorithmic tradition. Basically, let G = (V (G), E(G), w) be an n-vertex and m-edge 2-edgeconnected undirected graph, with edge-weight function w : E(G) → R + , and assume we are given a spanning tree T of G, which was computed by addressing some criterion (i.e., objective function) φ. Then, the problem is that of computing a BSE for every edge e ∈ E(T ), namely an edge f ∈ E(G) \ E(T ) such that the swap tree T e/f obtained by swapping e with f in T optimizes some objective function φ out of all possible swap trees. Quite reasonably, the function φ must be related (if not coinciding at all) with φ. The first immediate motivation for studying an ABSE problem comes from the edge fault-tolerance setting -a commonly accepted framework. Broadly speaking, the algorithmic question here is to design sparse subgraphs that guarantee a proper level of functionality even in the presence of an edge failure. In such a context, the rationale of an ABSE-based solution is the following: operations are normally performed on a (possibly optimal) spanning
Recently, in REF the authors designed a very clever recursive algorithm that uses centroid-decomposition techniques and lower envelope data structures to solve the ABSE problem on tree spanners in O(n 2 log 4 n) time and O(n 2 + m log 2 n) space.
An Improved Algorithm for Computing All the Best Swap Edges of a Tree Spanner
ArXiv
ArXiv
Computer Science Mathematics