Parallel Multilevel Algorithms for Multi-Constraint Graph Partitioning

Thumbnail Image

View/Download File

Persistent link to this item

View Statistics

Journal Title

Journal ISSN

Volume Title


Parallel Multilevel Algorithms for Multi-Constraint Graph Partitioning

Published Date






Recently, serial multi-constraint graph partitioning algorithms have been developed that are able to compute high-quality partitionings for emerging multi-phase, multi-mesh, and multi-physics problems. While these results are promising, the fact that these algorithms are serial limits the problem size that can be solved due to both solution time and memory requirements. A parallel multi-constraint graph partitioner will allow the partitioning of larger multi-constraint graphs, and therefore, is key to the efficient execution of large multi-phase, multi-mesh, and multi-physics problems. In this paper, we present a parallel multi-constraint graph partitioning algorithm based on the multilevel graph partitioning paradigm. We describe this algorithm and give experimental results conducted on a 128-processor Cray T3E. We show that our parallel algorithm is able to robustly compute balanced partitionings of similar quality to serial multi-constraint algorithms, while being scalable to very large graphs. We show that the run time of our algorithm is very fast. Our parallel multi-constraint graph partitioner is able to compute a three-constraint 128-way partitioning of a 7.5 million node graph in about 7 seconds on 128 processors of a Cray T3E.



Related to



Series/Report Number

Funding information

Isbn identifier

Doi identifier

Previously Published Citation

Suggested citation

Kumar, Vipin; Karypis, George; Schloegel, Kirk. (1999). Parallel Multilevel Algorithms for Multi-Constraint Graph Partitioning. Retrieved from the University Digital Conservancy,

Content distributed via the University Digital Conservancy may be subject to additional license and use restrictions applied by the depositor. By using these files, users agree to the Terms of Use. Materials in the UDC may contain content that is disturbing and/or harmful. For more information, please see our statement on harmful content in digital repositories.