The beta version of DROPS 2 is now publicly available! Check this page out at DROPS 2 now!


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.APPROX-RANDOM.2014.1
URN: urn:nbn:de:0030-drops-46857
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2014/4685/
Go to the corresponding LIPIcs Volume Portal

Abraham, Ittai ; Chechik, Shiri ; Talwar, Kunal

Fully Dynamic All-Pairs Shortest Paths: Breaking the O(n) Barrier

pdf-format:
2.pdf (0.5 MB)

Abstract

A fully dynamic approximate distance oracle is a distance reporting data structure that supports dynamic insert edge and delete edge operations. In this paper we break a longstanding barrier in the design of fully dynamic all-pairs approximate distance oracles.
All previous results for this model incurred an amortized cost of at least Omega(n) per operation. We present the first construction that provides constant stretch and o(m) amortized update time. For graphs that are not too dense (where |E| = O(|V|^{2-delta}) for some delta>0 we break the O(n) barrier and provide the first construction with constant stretch and o(n) amortized cost.

BibTeX - Entry

@InProceedings{abraham_et_al:LIPIcs:2014:4685,
  author =	{Ittai Abraham and Shiri Chechik and Kunal Talwar},
  title =	{{Fully Dynamic All-Pairs Shortest Paths: Breaking the O(n) Barrier}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2014)},
  pages =	{1--16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-74-3},
  ISSN =	{1868-8969},
  year =	{2014},
  volume =	{28},
  editor =	{Klaus Jansen and Jos{\'e} D. P. Rolim and Nikhil R. Devanur and Cristopher Moore},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2014/4685},
  URN =		{urn:nbn:de:0030-drops-46857},
  doi =		{10.4230/LIPIcs.APPROX-RANDOM.2014.1},
  annote =	{Keywords: Shortest Paths, Dynamic Algorithms}
}

Keywords: Shortest Paths, Dynamic Algorithms
Collection: Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2014)
Issue Date: 2014
Date of publication: 04.09.2014

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