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.2018.7
URN: urn:nbn:de:0030-drops-99557
URL: https://drops.dagstuhl.de/opus/volltexte/2018/9955/
Bilò, Davide ; Papadopoulos, Kleitos
A Novel Algorithm for the All-Best-Swap-Edge Problem on Tree Spanners
| pdf-format: |
|
Abstract
Given a 2-edge connected, unweighted, and undirected graph G with n vertices and m edges, a sigma-tree spanner is a spanning tree T of G in which the ratio between the distance in T of any pair of vertices and the corresponding distance in G is upper bounded by sigma. The minimum value of sigma for which T is a sigma-tree spanner of G is also called the stretch factor of T. We address the fault-tolerant scenario in which each edge e of a given tree spanner may temporarily fail and has to be replaced by a best swap edge, i.e. an edge that reconnects T-e at a minimum stretch factor. More precisely, we design an O(n^2) time and space algorithm that computes a best swap edge of every tree edge. Previously, an O(n^2 log^4 n) time and O(n^2+m log^2n) space algorithm was known for edge-weighted graphs [Bilò et al., ISAAC 2017]. Even if our improvements on both the time and space complexities are of a polylogarithmic factor, we stress the fact that the design of a o(n^2) time and space algorithm would be considered a breakthrough.
BibTeX - Entry
@InProceedings{bil_et_al:LIPIcs:2018:9955,
author = {Davide Bil{\`o} and Kleitos Papadopoulos},
title = {{A Novel Algorithm for the All-Best-Swap-Edge Problem on Tree Spanners}},
booktitle = {29th International Symposium on Algorithms and Computation (ISAAC 2018)},
pages = {7:1--7:12},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-094-1},
ISSN = {1868-8969},
year = {2018},
volume = {123},
editor = {Wen-Lian Hsu and Der-Tsai Lee and Chung-Shou Liao},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2018/9955},
URN = {urn:nbn:de:0030-drops-99557},
doi = {10.4230/LIPIcs.ISAAC.2018.7},
annote = {Keywords: Transient edge failure, best swap edges, tree spanner}
}
| Keywords: | Transient edge failure, best swap edges, tree spanner | |
| Seminar: | 29th International Symposium on Algorithms and Computation (ISAAC 2018) | |
| Issue date: | 2018 | |
| Date of publication: | 06.12.2018 |
