Bilò, Davide ;
Papadopoulos, Kleitos
A Novel Algorithm for the AllBestSwapEdge Problem on Tree Spanners
Abstract
Given a 2edge connected, unweighted, and undirected graph G with n vertices and m edges, a sigmatree 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 sigmatree spanner of G is also called the stretch factor of T. We address the faulttolerant 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 Te 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 edgeweighted 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 AllBestSwapEdge Problem on Tree Spanners}},
booktitle = {29th International Symposium on Algorithms and Computation (ISAAC 2018)},
pages = {7:17:12},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959770941},
ISSN = {18688969},
year = {2018},
volume = {123},
editor = {WenLian Hsu and DerTsai Lee and ChungShou Liao},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2018/9955},
URN = {urn:nbn:de:0030drops99557},
doi = {10.4230/LIPIcs.ISAAC.2018.7},
annote = {Keywords: Transient edge failure, best swap edges, tree spanner}
}
2018
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: 

2018 