Small Stretch Spanners on Dynamic Graphs
Vol. 10, no. 2, pp. 365-385, 2006. Regular paper.
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.