In Proceedings of the 11th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), San Francisco, California, Jan. 2000, pp. 859-860.

Available as: [ pdf, pdf.gz, ps, ps.Z, ps.gz ]

On External Memory Graph Traversal

by Adam L. Buchsbaum and Michael Goldwasser and Suresh Venkatasubramanian and Jeffery R. Westbrook

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.

Michael Goldwasser