ALCOMFT-TR-01-96

Ulrich Meyer
External Memory BFS on Undirected Graphs with Bounded Degree
MPI. Work package 1. May 2001.

Abstract: We give the first external memory algorithm for breadth-first search (BFS) which achieves o(n) I/Os on arbitrary undirected graphs with n nodes and maximum node degree d. Let M and B>d denote the main memory size and block size, respectively. Using \mathrmSort(x)=Theta(x/(B)· log_M/Bx/(B)), our algorithm needs O(n/(gamma · log_d B) + \mathrmSort(n · B^gamma)) I/Os and O(n · B^gamma) external space for an arbitrary parameter 0 <gamma <= 1/2. The result carries over to BFS, depth-first search (DFS) and single source shortest paths (SSSP) on undirected planar graphs with arbitrary node degrees.

Postscript file: ALCOMFT-TR-01-96.ps.gz (47 kb).