Small Stretch Spanners on Dynamic Graphs

Authors

  • Giorgio Ausiello
  • Paolo Franciosa
  • Giuseppe Italiano

DOI:

https://doi.org/10.7155/jgaa.00133

Keywords:

graph algorithms , dynamic algorithms , graph spanners

Abstract

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(n3/2) edges (resp., O(n4/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 ·n3/2) edges (resp., O(d ·n4/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.

Downloads

Download data is not yet available.

Downloads

Published

2006-01-01

How to Cite

Ausiello, G., Franciosa, P., & Italiano, G. (2006). Small Stretch Spanners on Dynamic Graphs. Journal of Graph Algorithms and Applications, 10(2), 365–385. https://doi.org/10.7155/jgaa.00133

Issue

Section

Articles

Categories