2000•Unpublished venueRequires access
On external memory graph traversal
Adam L. Buchsbaum, Michael H. Goldwasser, Suresh Venkatasubramanian, Jeffery Westbrook
Open publisher page 107 citations
Abstract
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...