Chapter 16 External-Memory Graph Algorithms Yi- Jen Chiang*l Abstract

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: Proximate-neighboring. We present a simple method for deriving external-memory lower bounds via reductions from a problem we call the “proxi-mate neighbors ” problem. We use this technique to derive non-trivial lower bounds for such problems as list ranking, expression tree evaluation, and con-nected components. PRAM simulation. We give methods for efficiently simulating PRAM computations in external mem-ory, even for some cases in which the PRAM algo-rithm is not work-optimal. We apply this to derive a number of optimal (and simple) external-memory graph algorithms. Time-forward processing. We present a general technique for evaluating circuits (or “circuit-like” computations) in external memory. We also us