ALCOMFT-TR-02-48

Kurt Mehlhorn and Ulrich Meyer
External-Memory Breadth-First Search with Sublinear I/O
MPI. Work package 1. May 2002.

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 Theta(\nodes + (n + m)/(D · B) · log_M/B (n + m)/(B)) 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( \ourbound ) I/Os (expected or worst-case, respectively). Hence, for \edges = O(\nodes), 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. We also give an improved single-source shortest-paths algorithm for small integer edge weights.

Postscript file: ALCOMFT-TR-02-48.ps.gz (97 kb).