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 |
