External-memory depth-first search algorithm for solid grid graphs
In this paper. we propose an external memory depth first search algorithm for solid grid graphs, a subclass of grid graphs. The I/O-complexity of the algorithm, is O(sort(N)), where N = \V\ + \E\, sort(N) = Theta(N/B log (M/B) N/B) is the sorting I/O-complexity. M is the memory size, and B is the block size. Since grid graphs might be nonplanar (if diagonal edges intersect), they are beyond the reach of existing planar depth first search algorithms. The best known algorithm for this class of graph is the standard (internal memory) DFS algorithm with appropriate block (sub-grid) I/O-access. Its I/O-complexity is O(N/rootB). (C) 2004 Elsevier B.V. All rights reserved.
i/o-complexity external-memory algorithms graph algorithms