LIPIcs.STACS.2008.1316.pdf
- Filesize: 227 kB
- 10 pages
Document
On Dynamic Breadth-First Search in External-Memory
Author
-
Part of:
Volume:
25th International Symposium on Theoretical Aspects of Computer Science (STACS 2008)
Series: Leibniz International Proceedings in Informatics (LIPIcs)
Conference: Symposium on Theoretical Aspects of Computer Science (STACS) - License:
Creative Commons Attribution-NoDerivs 3.0 Unported license
- Publication Date: 2008-02-06
Cite AsGet BibTex
Ulrich Meyer. On Dynamic Breadth-First Search in External-Memory. In 25th International Symposium on Theoretical Aspects of Computer Science. Leibniz International Proceedings in Informatics (LIPIcs), Volume 1, pp. 551-560, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2008)
https://doi.org/10.4230/LIPIcs.STACS.2008.1316
https://doi.org/10.4230/LIPIcs.STACS.2008.1316
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.
Keywords
- External Memory
- Dynamic Graph Algorithms
- BFS
- Randomization
Metrics
- Access Statistics
-
Total Accesses (updated on a weekly basis)
0PDF Downloads