On external memory graph traversal
On external memory graph traversal
复制标题
DOI：
--
复制
发表时间：
2000-02
期刊：
影响因子：
--
通讯作者：
A. Buchsbaum;Michael H. Goldwasser;Suresh Venkatasubramanian;J. Westbrook
中科院分区：
文献类型：
--
作者：
A. Buchsbaum;Michael H. Goldwasser;Suresh Venkatasubramanian;J. 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.
