License: Creative Commons Attribution-NoDerivs 3.0 Unported license (CC BY-ND 3.0)
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://dagstuhl.sunsite.rwth-aachen.de/volltexte/2008/1316/
Go to the corresponding LIPIcs Volume Portal

Meyer, Ulrich

On Dynamic Breadth-First Search in External-Memory

pdf-format:
22011.MeyerUlrich.Paper.1316.pdf (0.2 MB)

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},
  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 =		{10.4230/LIPIcs.STACS.2008.1316},
  annote =	{Keywords: External Memory, Dynamic Graph Algorithms, BFS, Randomization}
}

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

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