On Dynamic Breadth-First Search in External-Memory

Author Ulrich Meyer



PDF
Thumbnail PDF

File

LIPIcs.STACS.2008.1316.pdf
  • Filesize: 227 kB
  • 10 pages

Document Identifiers

Author Details

Ulrich Meyer

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

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)
    0
    PDF Downloads
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail