A functional approach to external graph algorithms

Abstract. We present a new approach for designing external graph algorithms and use it to design simple external algorithms for computing connected compo-nents, minimum spanning trees, bottleneck minimum spanning trees, and maxi-mal matchings in undirected graphs and multi-graphs. Our I/O bounds compete with those of previous approaches. Unlike previous approaches, ours is purely functional—without side effects—and is thus amenable to standard checkpoint-ing and programming language optimization techniques. This is an important practical consideration for applications that may take hours to run.