hide
Free keywords:
Computer Science, Data Structures and Algorithms, cs.DS
Abstract:
An $\alpha$-spanner of a graph $ G $ is a subgraph $ H $ such that $ H $
preserves all distances of $ G $ within a factor of $ \alpha $. In this paper,
we give fully dynamic algorithms for maintaining a spanner $ H $ of a graph $ G
$ undergoing edge insertions and deletions with worst-case guarantees on the
running time after each update. In particular, our algorithms maintain: (1) a
$3$-spanner with $ \tilde O (n^{1+1/2}) $ edges with worst-case update time $
\tilde O (n^{3/4}) $, or (2) a $5$-spanner with $ \tilde O (n^{1+1/3}) $ edges
with worst-case update time $ \tilde O (n^{5/9}) $. These size/stretch
tradeoffs are best possible (up to logarithmic factors). They can be extended
to the weighted setting at very minor cost. Our algorithms are randomized and
correct with high probability against an oblivious adversary. We also further
extend our techniques to construct a $5$-spanner with suboptimal size/stretch
tradeoff, but improved worst-case update time.
To the best of our knowledge, these are the first dynamic spanner algorithms
with sublinear worst-case update time guarantees. Since it is known how to
maintain a spanner using small amortized but large worst-case update time
[Baswana et al. SODA'08], obtaining algorithms with strong worst-case bounds,
as presented in this paper, seems to be the next natural step for this problem.