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

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.