2026-07-26T20:01:55Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:1316 2024-03-06T10:33:02Z ddc:004 open_access

On Dynamic Breadth-First Search in External-Memory Meyer, Ulrich External Memory Dynamic Graph Algorithms BFS Randomization 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Ulrich Meyer 2008 Is Part Of LIPIcs, Volume 1, 25th International Symposium on Theoretical Aspects of Computer Science (2008) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.STACS.2008.1316 urn:nbn:de:0030-drops-13167 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2008.1316 eng https://creativecommons.org/licenses/by-nd/3.0/legalcode