Biḷ, Davide ;
Colella, Feliciano ;
Gualà, Luciano ;
Leucci, Stefano ;
Proietti, Guido
An Improved Algorithm for Computing All the Best Swap Edges of a Tree Spanner
Abstract
A tree sigmaspanner of a positively realweighted nvertex and medge 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, setup 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 wellestablished 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.
BibTeX  Entry
@InProceedings{bil_et_al:LIPIcs:2017:8266,
author = {Davide Bil{\`o} and Feliciano Colella and Luciano Gual{\`a} and Stefano Leucci and Guido Proietti},
title = {{An Improved Algorithm for Computing All the Best Swap Edges of a Tree Spanner}},
booktitle = {28th International Symposium on Algorithms and Computation (ISAAC 2017)},
pages = {14:114:13},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959770545},
ISSN = {18688969},
year = {2017},
volume = {92},
editor = {Yoshio Okamoto and Takeshi Tokuyama},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2017/8266},
URN = {urn:nbn:de:0030drops82663},
doi = {10.4230/LIPIcs.ISAAC.2017.14},
annote = {Keywords: Transient edge failure, Swap algorithm, Tree spanner}
}
2017
Keywords: 

Transient edge failure, Swap algorithm, Tree spanner 
Seminar: 

28th International Symposium on Algorithms and Computation (ISAAC 2017)

Issue date: 

2017 
Date of publication: 

2017 