External-memory graph algorithms
Yi‐Jen Chiang, Michael T. Goodrich, Edward F. Grove et al. · KU ScholarWorks (University of Kansas) · 1995
We present a collection of new techniques for designing and analyzing efficient external-memory algorithms for graph problems and illustrate how these techniques can be applied to a wide variety of specific problems. Our results include:\nProximate-neighboring. We present a simple\nmethod for deriving external-memory lower bounds\nvia reductions from a problem we call the “proximate neighbors” problem. We use this technique to derive non-trivial lower bounds for such problems as list ranking, expression tree evaluation, and connected components. PRAM simulation. We give methods for efficiently\nsimulating PRAM computations in external memory, even for some cases in which the PRAM algorithm is not work-optimal. We apply this to derive a number of optimal (and simple) external-memory graph algorithms.\nTime-forward processing. We present a general\ntechnique for evaluating circuits (or “circuit-like”\ncomputations) in external memory. We also usethis in a deterministic list ranking algorithm.\nDeterministic 3-coloring of a cycle. We give\nseveral optimal methods for 3-coloring a cycle,\nwhich can be used as a subroutine for finding large\nindependent sets for list ranking. Our ideas go\nbeyond a straightforward PRAM simulation, and\nmay be of independent interest.\nExternal depth-first search. We discuss a method\nfor performing depth first search and solving related\nproblems efficiently in external memory. Our\ntechnique can be used in conjunction with ideas\ndue to Ullman and Yannakakis in order to solve\ngraph problems involving closed semi-ring computations even when their assumption that vertices fit in main memory does not hold.\nOur techniques apply to a number of problems, including list ranking, which we discuss in detail, finding Euler tours, expression-tree evaluation, centroid decomposition of a tree, least-common ancestors, minimum spanning tree verification, connected and biconnected components, minimum spanning forest, ear decomposition, topological sorting, reachability, graph drawing, and visibility representation.
Cited by 275 works. doi:10.5555/313651.313681 Open-access PDF
Authors
- Yi‐Jen Chiang
- Michael T. Goodrich
- Edward F. Grove
- Roberto Tamassia
- Darren Erik Vengroff
- Jeffrey Scott Vitter
References
- An introduction to disk drive modeling
- The input/output complexity of sorting and related problems
- Deterministic coin tossing with applications to optimal parallel list ranking
- Algorithms for parallel memory, I: Two-level memories
- Finding biconnected componemts and computing tree functions in logarithmic parallel time
- Efficient parallel algorithms for some graph problems
- External-memory computational geometry
- Deterministic distribution sort in shared and distributed memory multiprocessors
- Recursive Star-Tree Parallel Data Structure
- A randomized linear-time algorithm for finding minimum spanning trees