License
when quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.STACS.2008.1316
URN: urn:nbn:de:0030-drops-13167
URL: http://drops.dagstuhl.de/opus/volltexte/2008/1316/
Meyer, Ulrich

On Dynamic Breadth-First Search in External-Memory

pdf-format:
Dokument 1.pdf (227 KB)

Abstract

We provide the first non-trivial result on dynamic breadth-first search (BFS) in external-memory: For general sparse undirected graphs of initially $n$ nodes and $O(n)$ edges and monotone update sequences of either $Theta(n)$ edge insertions or $Theta(n)$ edge deletions, we prove an amortized high-probability bound of $O(n/B^{2/3}+sort(n)cdot log B)$ I/Os per update. In contrast, the currently best approach for static BFS on sparse undirected graphs requires $Omega(n/B^{1/2}+sort(n))$ I/Os.

BibTeX - Entry

@InProceedings{meyer:LIPIcs:2008:1316,
  author =	{Ulrich Meyer},
  title =	{On Dynamic Breadth-First Search in External-Memory},
  booktitle =	{25th International Symposium on Theoretical Aspects of Computer Science (STACS 2008)},
  pages =	{551--560},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-06-4},
  ISSN =	{1868-8969},
  year =	{2008},
  volume =	{1},
  editor =	{Susanne Albers and Pascal Weil},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2008/1316},
  URN =		{urn:nbn:de:0030-drops-13167},
  doi =		{http://dx.doi.org/10.4230/LIPIcs.STACS.2008.1316},
  annote =	{Keywords: External Memory, Dynamic Graph Algorithms, BFS, Randomization}
}

Keywords: External Memory, Dynamic Graph Algorithms, BFS, Randomization
Seminar: 25th International Symposium on Theoretical Aspects of Computer Science
Issue date: 2008
Date of publication: 06.02.2008

DROPS-Home | Fulltext Search | Imprint Published by LZI