On dynamic breadth-first search in external-memory
- 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. 1998 ACM Subject Classification: F.2.2. Key words and phrases: External Memory, Dynamic Graph Algorithms, BFS, Randomization.
Author: | Ulrich MeyerORCiDGND |
---|---|
URN: | urn:nbn:de:hebis:30-74322 |
ArXiv Id: | http://arxiv.org/abs/0802.2847 |
Parent Title (English): | Symposium on Theoretical Aspects of Computer Science 2008 (Bordeaux) |
Document Type: | Article |
Language: | English |
Date of Publication (online): | 2010/01/22 |
Year of first Publication: | 2008 |
Publishing Institution: | Universitätsbibliothek Johann Christian Senckenberg |
Release Date: | 2010/01/22 |
Tag: | BFS; Dynamic Graph Algorithms; External Memory; Randomization |
Page Number: | 10 |
First Page: | 551 |
Last Page: | 560 |
Note: | (c) U. Meyer ; CC Creative Commons Attribution-NoDerivs License |
Source: | Dans Proceedings of the 25th Annual Symposium on the Theoretical Aspects of Computer Science - STACS 2008, Bordeaux : France (2008) |
HeBIS-PPN: | 221135316 |
Institutes: | Informatik und Mathematik / Informatik |
Dewey Decimal Classification: | 0 Informatik, Informationswissenschaft, allgemeine Werke / 00 Informatik, Wissen, Systeme / 004 Datenverarbeitung; Informatik |
Licence (German): | Creative Commons - Namensnennung-Keine Bearbeitung |