External Memory BFS on Undirected Graphs with Bounded Degree
Ulrich Meyer · 2001
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 Sort(x) = O( ~.IOgM/B ~), our algorithm needs O(~.1o ~ B "-b Sort(n. BY)) I/Os and O(n. B Y) external space for an arbitrary parameter 0 <-/_< 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. 1 Introduct ion We use the standard I/O model of [1], which counts accesses to a disk of potentially infinite size using the parameters M for the memory size and B for the block size where B < M/2. Let Sort(x) = O( ~.lOgM/B ~) denote the number of I/Os needed to sort x items, and Scan(x) = [~] the number of I/Os required to transfer x items between contiguous disk positions and internal memory. Given a graph G with n nodes and m edges the model applies when M < n < m. The best known external memory algorithms for breadth-first search (BFS), depth-first search (DFS) and single-source shortest paths (SSSP) on general undirected graphs still require f~(n) I/Os, even if the graphs are planar and/or have bounded node degrees: O(n+~.Sor t (n) ) I/Os for BFS [4], O(n+~-log ~) I/Os for SSSP [3], and O(min{~-~. ~ +n, (n+~). log ~}) I/Os for DFS [6]. Better algorithms are known for special graph classes, see [6] for an overview. Furthermore, there is an O(Sort(n)) I /O algorithm for SSSP on undirected planar graphs G with bounded degree [2]. However, it requires a BFS-tree for G as part of the input. New Results. We show how a modification of the BFS algorithm of Munagala and Ranade [4] can take advantage of a redundant graph representation. For arbitrary undirected graphs with maximum node degree d < B we obtain an O(~' * + Sort(n • B~)) I /O-~-P lanck- Ins t i tu t f/Jr Informatik, Stuhlsatzenausweg 85,