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

摘要

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 Θ(n + (n+m)/(D·B)·log_(M/B)(m+n)/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 a new approach which requires only O((n·(n+m)/(D·B))~(1/2) + (n+m)/(D·B)·log_(M/B)(m+n)/B)I/Os. Hence, for m = O(n) and all realistic values of log_(M/B) (n+m)/B, it improves upon the I/O-performance of the best previous algorithm by a factor Ω((D·B)~(1/2)). Our approach is fairly simple and we conjecture it to be practical. We also give improved algorithms for undirected single-source shortest-paths with small integer edge weights and for semi-external BFS on directed Eulerian graphs.