License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ISAAC.2017.14
URN: urn:nbn:de:0030-drops-82663
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2017/8266/
Go to the corresponding LIPIcs Volume Portal

Bilò, Davide ; Colella, Feliciano ; Gualà, Luciano ; Leucci, Stefano ; Proietti, Guido

An Improved Algorithm for Computing All the Best Swap Edges of a Tree Spanner

pdf-format:
LIPIcs-ISAAC-2017-14.pdf (0.7 MB)

Abstract

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.

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:1--14:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-054-5},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{92},
  editor =	{Yoshio Okamoto and Takeshi Tokuyama},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2017/8266},
  URN =		{urn:nbn:de:0030-drops-82663},
  doi =		{10.4230/LIPIcs.ISAAC.2017.14},
  annote =	{Keywords: Transient edge failure, Swap algorithm, Tree spanner}
}

Keywords: Transient edge failure, Swap algorithm, Tree spanner
Collection: 28th International Symposium on Algorithms and Computation (ISAAC 2017)
Issue Date: 2017
Date of publication: 07.12.2017

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI