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: https://drops.dagstuhl.de/opus/volltexte/2008/1316/
Meyer, Ulrich
On Dynamic Breadth-First Search in External-Memory
| pdf-format: |
|
Abstract
We provide the first non-trivial result on dynamic breadth-firstsearch (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 | |
| Seminar: | 25th International Symposium on Theoretical Aspects of Computer Science | |
| Issue date: | 2008 | |
| Date of publication: | 06.02.2008 |
