z-logo
open-access-imgOpen Access
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

The content you want is available to Zendy users.

Already have an account? Click here to sign in.
Having issues? You can contact us here