Graph Partitioning Algorithms for Distributing Workloads of Parallel Computations

Bradford L. Chamberlain

University of Washington Technical Report UW-CSE-98-10-03
(generals exam for Bradford L. Chamberlain)

Abstract: This paper surveys graph partitioning algorithms used for parallel computing, with an emphasis on the problem of distributing workloads for parallel computations. Geometric, structural, and refinement-based algorithms are described and contrasted. In addition, multilevel partitioning techniques and issues related to parallel partitioning are addressed. All algorithms are evaluated qualitatively in terms of their execution speed and ability to generate partitions with small separators.

postscript | PDF
Color Plate : gzipped postscript