A Functional Approach to External Graph Algorithms

A Functional Approach to External Graph Algorithms

0.00 Avg rating0 Votes
Article ID: iaor20121101
Volume: 32
Issue: 3
Start Page Number: 437
End Page Number: 458
Publication Date: Mar 2002
Journal: Algorithmica
Authors: , ,
Keywords: optimization
Abstract:

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 forests, bottleneck minimum spanning forests, maximal independent sets (randomized only), and maximal matchings in undirected graphs. 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.

Reviews

Required fields are marked *. Your email address will not be published.