Small Stretch Spanners on Dynamic Graphs
Giorgio Ausiello, Paolo Giulio Franciosa, Giuseppe Francesco Italiano · Journal of Graph Algorithms and Applications · 2006
Abstract. We present fully dynamic algorithms for maintaining 3- and 5-spanners of undirected graphs. For unweighted graphs we maintain a 3or 5-spanner under insertions and deletions of edges in O(n) amortized time per operation over a sequence of Ω(n) updates. The maintained 3-spanner (resp., 5-spanner) has O(n 3/2) edges (resp., O(n 4/3)edges), which is known to be optimal. On weighted graphs with d different edge cost values, we maintain a 3- or 5-spanner in O(n) amortized time per operation over a sequence of Ω(d·n) updates. The maintained 3-spanner (resp., 5-spanner) has O(d·n 3/2) edges (resp., O(d·n 4/3)edges).Thesame approach can be extended to graphs with real-valued edge costs in the range [1,C]. All our algorithms are deterministic and are substantially faster than recomputing a spanner from scratch after each update. 1