2026-08-14T03:59:54Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:8266 2024-03-06T10:41:47Z ddc:004 open_access

An Improved Algorithm for Computing All the Best Swap Edges of a Tree Spanner Bilò, Davide Colella, Feliciano Gualà, Luciano Leucci, Stefano Proietti, Guido Transient edge failure Swap algorithm Tree spanner 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Davide Bilò and Feliciano Colella and Luciano Gualà and Stefano Leucci and Guido Proietti 2017 Is Part Of LIPIcs, Volume 92, 28th International Symposium on Algorithms and Computation (ISAAC 2017) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ISAAC.2017.14 urn:nbn:de:0030-drops-82663 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2017.14 eng https://creativecommons.org/licenses/by/3.0/legalcode