2026-08-02T00:56:26Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:9955 2024-03-06T10:45:12Z ddc:004 open_access

A Novel Algorithm for the All-Best-Swap-Edge Problem on Tree Spanners Bilò, Davide Papadopoulos, Kleitos Transient edge failure best swap edges tree spanner 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Davide Bilò and Kleitos Papadopoulos 2018 Is Part Of LIPIcs, Volume 123, 29th International Symposium on Algorithms and Computation (ISAAC 2018) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ISAAC.2018.7 urn:nbn:de:0030-drops-99557 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2018.7 eng https://creativecommons.org/licenses/by/3.0/legalcode