
Small Stretch Spanners on Dynamic Graphs
Author(s) -
Giorgio Ausiello,
Paolo Giulio Franciosa,
Giuseppe F. Italiano
Publication year - 2006
Publication title -
journal of graph algorithms and applications
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.387
H-Index - 38
ISSN - 1526-1719
DOI - 10.7155/jgaa.00133
Subject(s) - computer science , combinatorics , mathematics
We present fully dynamic algorithms for maintaining 3- and 5-spanners of undirected graphs under a sequence of update operations. For unweighted graphs we maintain a 3-spanner or a 5-spanner under insertions and deletions of edges; on a graph with n vertices each operation is performed in O(Δ) amortized time over a sequence of Ω(n) updates, where Δ is the maximum degree of the original graph. 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 within the same amortized time bounds 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). The same 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