In Proceedings of the 11th Annual ACM-SIAM Symposium on
Discrete Algorithms (SODA), San Francisco, California, Jan. 2000, pp. 859-860.
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
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.