Tech Report CS-92-44
Blocking for External Graph Searching
Mark H. Nodine, Michael T. Goodrich, and Jeffrey Scott Vitter
September 1992
Abstract:
In this paper we consider the problem of using disk blocks efficiently in searching graphs that are too large to fit in internal memory. Our model allows a vertex to be represented any number of times on the disk in order to take advantage of redundancy. We give matching upper and lower bounds for complete d-ary trees and d-dimensional grid graphs, as well as for classes of general graphs that intuitively speaking have a close to uniform number of neighbors around each vertex.(complete text in pdf or gzipped postscript)
| Page Owner: John Bazik | Last Modified: Fri Feb 9 17:44:33 2007 |