×

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].

MSC:

68P05 Data structures
PDFBibTeX XMLCite