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/
 Go to the corresponding LIPIcs Volume Portal

### 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},