Given a 2-edge connected, unweighted, and undirected graph G with n vertices and m edges, a σ-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 σ. The minimum value of σ for which T is a σ-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(n2) time and space algorithm that computes a best swap edge of every tree edge. Previously, an O(n2 log4 n) time and O(n2 + mlog2 n) 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(n2) time and space algorithm would be considered a breakthrough.
A novel algorithm for the all-best-swap-edge problem on tree spanners / Bilo, D.; Papadopoulos, K.. - 123:(2018), pp. 7-:1–7:12. (Intervento presentato al convegno 29th International Symposium on Algorithms and Computation, ISAAC 2018 tenutosi a twn nel 2018) [10.4230/LIPIcs.ISAAC.2018.7].
A novel algorithm for the all-best-swap-edge problem on tree spanners
Bilo D.;
2018-01-01
Abstract
Given a 2-edge connected, unweighted, and undirected graph G with n vertices and m edges, a σ-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 σ. The minimum value of σ for which T is a σ-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(n2) time and space algorithm that computes a best swap edge of every tree edge. Previously, an O(n2 log4 n) time and O(n2 + mlog2 n) 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(n2) time and space algorithm would be considered a breakthrough.I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
