On external memory graph traversal

We describe a new external memory data structure, the buffered repository tree, and use it to provide the first non-trivial external memory algorithm for directed breadth-first search (BFS) and an improved external algorithm for directed depth-first search. We also demonstrate the equivalence of various formulations of external undirected BFS, and we use these to give the first I/O-optimal BFS algorithm for undirected trees. 1 Introduction We use the standard I/O model 1, which counts disk accesses incurred by an algorithm, using the following parameters: M is the memory size, B is the block size, and we assume that B M=2. Define sort(N) = ( N B log M=B N B ), the number of I/Os needed to sort N items, and scan(N) = dN=Be, the number of I/Os needed to transfer N contiguous items between disk and internal memory. Given a graph with V vertices and E edges, the model applies when M V E. For undirected graphs, Kameshwar and Ranade 5 give an O(V + E V sort(V )) I/O algo...