Multilevel algorithms for multi-constraint graph partitioning

Research output: Chapter in Book/Report/Conference proceedingConference contribution

152 Scopus citations

Abstract

Traditional graph partitioning algorithms compute a k-way partitioning of a graph such that the number of edges that are cut by the partitioning is minimized and each partition has an equal number of vertices. The task of minimizing the edge-cut can be considered as the objective and the requirement that the partitions will be of the same size can be considered as the constraint. In this paper we extend the partitioning problem by incorporating an arbitrary number of balancing constraints. In our formulation, a vector of weights is assigned to each vertex, and the goal is to produce a k-way partitioning such that the partitioning satisfies a balancing constraint associated with each weight, while attempting to minimize the edge-cut. Applications of this multi-constraint graph partitioning problem include parallel solution of multi-physics and multi-phase computations, that underlay many existing and emerging large-scale scientific simulations. We present new multi-constraint graph partitioning algorithms that are based on the multilevel graph partitioning paradigm. Our work focuses on developing new types of heuristics for coarsening, initial partitioning, and refinement that are capable of successfully handling multiple constraints. We experimentally evaluate the effectiveness of our multi-constraint partitioners on a variety of synthetically generated problems.

Original languageEnglish (US)
Title of host publicationSC 1998 - Proceedings of the ACM/IEEE Conference on Supercomputing
PublisherAssociation for Computing Machinery
ISBN (Electronic)081868707X
DOIs
StatePublished - 1998
Event1998 ACM/IEEE Conference on Supercomputing, SC 1998 - Orlando, United States
Duration: Nov 7 1998Nov 13 1998

Publication series

NameProceedings of the International Conference on Supercomputing
Volume1998-November

Conference

Conference1998 ACM/IEEE Conference on Supercomputing, SC 1998
Country/TerritoryUnited States
CityOrlando
Period11/7/9811/13/98

Bibliographical note

Funding Information:
The formulation of the multi-objective multi-constraint graph partitioning problem was motivated by discussion with Raju Namburu, Carol Hoover, and David Keys. We also like to thank Bruce Hendrickson for his valuable comments on an early draft of this paper. This work was supported by NSF CCR-9423082 and by Army Research Office contract DA/DAAH04-95-1-0538, and by Army High Performance Computing Research Center under the auspices of the Department of the Army, Army Research Laboratory cooperative agreement number DAAH04-95-2-0003/contract number DAAH04-95-C-0008, the content of which does not necessarily reflect the position or the policy of the government, and no official endorsement should be inferred. Access to computing facilities was provided by AHPCRC, Minnesota Supercomputer Institute, Cray Research Inc, and by the Pittsburgh Supercomputing Center. Related papers are available via WWW at URL: http://www.cs.umn.edu/~karypis

Publisher Copyright:
© 1998 IEEE.

Keywords

  • Graph partitioning
  • Numerical simulations
  • Parallel processing

Fingerprint

Dive into the research topics of 'Multilevel algorithms for multi-constraint graph partitioning'. Together they form a unique fingerprint.

Cite this