2017/10/04 by Davide Bilò, Bilò, Davide, Feliciano Colella +7
Computer Science · #Advanced Graph Theory Research #Complexity and Algorithms in Graphs #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #G.2.2 #Interconnection Networks and Systems #cs.DS
paper · pdf · doi:10.48550/arxiv.1710.01516
17 pages, 4 figures, ISAAC 2017
arxiv created 2017/10/04 · openalex publication_date 2017/10/04 · arxiv updated 2017/10/05 · openalex created_date 2025/11/01 · openalex updated_date 2026/07/28
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(n2 log4 n) time, which drastically improves (almost by a quadratic factor in n in dense graphs!) on the previous known best result.