A new algorithm for multi-objective graph partitioning

Kirk Schloegel, George Karypis, Vipin Kumar

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

29 Scopus citations


Recently, a number of graph partitioning applications have emerged with additional requirements that the traditional graph partitioning model alone cannot effectively handle. One such class of problems is those in which multiple objectives, each of which can be modeled as a sum of weights of the edges of a graph, must be simultaneously optimized. This class of problems can be solved utilizing a multi-objective graph partitioning algorithm. We present a new formulation of the multi-objective graph partitioning problem and describe an algorithm that computes partitionings with respect to this formulation. We explain how this algorithm provides the user with a fine-tuned control of the tradeoffs among the objectives, results in predictable partitionings, and is able to handle both similar and dissimilar objectives. We show that this algorithm is better able to find a good tradeoff among the objectives than partitioning with respect to a single objective only. Finally, we show that by modifying the input preference vector, the multi-objective graph partitioning algorithm is able to gracefully tradeoff decreases in one objective for increases in the others.

Original languageEnglish (US)
Title of host publicationEuro-Par 1999 - Parallel Processing
Subtitle of host publication5th International Conference, Proceedings
PublisherSpringer Verlag
Number of pages10
ISBN (Print)3540664432, 9783540664437
StatePublished - 1999
Event5th International Conference on Parallel Processing, Euro-Par 1999 - Toulouse, France
Duration: Aug 31 1999Sep 3 1999

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume1685 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349


Other5th International Conference on Parallel Processing, Euro-Par 1999


Dive into the research topics of 'A new algorithm for multi-objective graph partitioning'. Together they form a unique fingerprint.

Cite this