external memory bfs on undirected graphs with bounded degree
We give the first external memory algorithm for breadth-first search (BFS) which achieves &Ogr; ( n ) I/Os on arbitrary undirected graphs with n nodes and maximum node degree d . Let M and B < d denote the main memory size and block size, respectively. Using Sort( x ) = &THgr;( x  B  log M / B x  B ), our algorithm needs &Ogr; ( n &ggr;log d B + Sort( n  B &ggr; )) I/Os and &Ogr; ( n  B &ggr; ) external space for an arbitrary parameter 0 < &ggr; &lne; . The result carries over to BFS, depth-first search (DFS) and single source shortest paths (SSSP) on undirected planar graphs with arbitrary node degrees.
memorialized graph algorithm search size blocking sorting log space shortest path planar graph