A Functional Approach to External Graph Algorithms

We present a new approach for designing external graph algorithms and use it to design simple deterministic and randomized external algorithms for computing connected components, minimum spanning trees, bottleneck minimum spanning trees, maximal independent sets (randomized only), and maximal matchings in undirected graphs and multigraphs. Our I/O bounds compete with those of previous approaches. We also introduce a semi-external model, in which the vertex set but not the edge set of a graph fits in main memory. In this model, we give an improved connected components algorithm, using new results for external grouping and sorting with duplicates. Unlike previous approaches, ours is purely functional---without side effects---and is thus amenable to standard checkpointing and programming language optimization techniques. This is an important practical consideration for applications that may take hours to run. L AT&T Labs---Research TR 99.1.1 Submitted for publication. An extended abst..