Buchsbaum, Adam L.; Goldwasser, Michael; Venkatasubramanian, Suresh; Westbrook, Jeffery R. On external memory graph traversal. (English) Zbl 0956.68037 Proceedings of the 11th annual ACM-SIAM symposium on Discrete algorithms. San Francisco, CA, USA, January 9-11, 2000. Philadelphia, PA: SIAM. 859-860 (2000). Summary: 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.For the entire collection see [Zbl 0933.00039]. Cited in 1 ReviewCited in 8 Documents MSC: 68P05 Data structures Keywords:external memory data structure; buffered repository tree PDFBibTeX XMLCite \textit{A. L. Buchsbaum} et al., in: Proceedings of the 11th annual ACM-SIAM symposium on discrete algorithms, SODA 2000, San Francisco, CA, USA, January 9--11, 2000. Philadelphia, PA: SIAM. 859--860 (2000; Zbl 0956.68037)