de.mpg.escidoc.pubman.appbase.FacesBean
English
 
Help Guide Disclaimer Contact us Login
  Advanced SearchBrowse

Item

ITEM ACTIONSEXPORT

Released

Conference Paper

External-Memory Breadth-First Search with Sublinear I/O

MPS-Authors
http://pubman.mpdl.mpg.de/cone/persons/resource/persons45021

Mehlhorn,  Kurt
Algorithms and Complexity, MPI for Informatics, Max Planck Society;

http://pubman.mpdl.mpg.de/cone/persons/resource/persons45038

Meyer,  Ulrich
Algorithms and Complexity, MPI for Informatics, Max Planck Society;

http://pubman.mpdl.mpg.de/cone/persons/resource/persons45250

Raman,  Rajeev
Algorithms and Complexity, MPI for Informatics, Max Planck Society;

Locator
There are no locators available
Fulltext (public)
There are no public fulltexts available
Supplementary Material (public)
There is no public supplementary material available
Citation

Mehlhorn, K., & Meyer, U. (2002). External-Memory Breadth-First Search with Sublinear I/O. In Algorithms - ESA 2002: 10th Annual European Symposium (pp. 723-735). Berlin, Germany: Springer.


Cite as: http://hdl.handle.net/11858/00-001M-0000-000F-2F7A-6
Abstract
Breadth-first search (BFS) is a basic graph exploration technique. We give the first external-memory algorithm for sparse undirected graphs with sublinear I/O. The best previous algorithm requires O( n + sort(n+m) ) I/Os on a graph with n nodes and m edges and a machine with main-memory of size M, D parallel disks, and block size B. We present two versions of a new algorithm which requires only O( sqrt( n/m * (n+m)/(D*B) ) * log_{M/B} (n/B) + sort(n+m)) I/Os (expected or worst-case, respectively). Hence, for m = O(n), they improve upon the I/O-performance of the best previous algorithm by nearly a factor of sqrt(D*B). Our approach is fairly simple and we conjecture at least the randomized version to be practical.