# Item

ITEM ACTIONSEXPORT

Released

Conference Paper

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

##### MPS-Authors

##### 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.