A Functional Approach to External Graph Algorithms |
| |
Authors: | Abello Buchsbaum and Westbrook |
| |
Affiliation: | (1) AT\&T Labs, Shannon Laboratory, 180 Park Ave., Florham Park, NJ 07932, USA. abello@research.\break att.com, alb@research.\break att.com., US;(2) 20th Century Television, Los Angeles, CA 90025, USA. jwestbrook@acm.org. Work completed while a member of AT\&T Labs., US |
| |
Abstract: | 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. |
| |
Keywords: | , Connected components, External memory algorithms, Graph algorithms, Maximal matchings, Maximal independent sets,,,,,,Minimum spanning trees, Functional programming, |
本文献已被 SpringerLink 等数据库收录! |
|