License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ESA.2016.17
URN: urn:nbn:de:0030-drops-63688
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2016/6368/
Go to the corresponding LIPIcs Volume Portal

Bodwin, Greg ; Krinninger, Sebastian

Fully Dynamic Spanners with Worst-Case Update Time

pdf-format:
LIPIcs-ESA-2016-17.pdf (0.5 MB)

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:

- a 3-spanner with ~O(n^{1+1/2}) edges with worst-case update time ~O(n^{3/4}), or

- a 5-spanner with ~O(n^{1+1/3}) edges with worst-case update time ~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.

BibTeX - Entry

@InProceedings{bodwin_et_al:LIPIcs:2016:6368,
  author =	{Greg Bodwin and Sebastian Krinninger},
  title =	{{Fully Dynamic Spanners with Worst-Case Update Time}},
  booktitle =	{24th Annual European Symposium on Algorithms (ESA 2016)},
  pages =	{17:1--17:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-015-6},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{57},
  editor =	{Piotr Sankowski and Christos Zaroliagis},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2016/6368},
  URN =		{urn:nbn:de:0030-drops-63688},
  doi =		{10.4230/LIPIcs.ESA.2016.17},
  annote =	{Keywords: Dynamic graph algorithms, spanners}
}

Keywords: Dynamic graph algorithms, spanners
Collection: 24th Annual European Symposium on Algorithms (ESA 2016)
Issue Date: 2016
Date of publication: 18.08.2016

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI