Analysis of multilevel graph partitioning

Research output: Contribution to journalConference articlepeer-review

109 Scopus citations


Recently, a number of researchers have investigated a class of algorithms that are based on multilevel graph partitioning that have moderate computational complexity, and provide excellent graph partitions. However, there exists little theoretical analysis that could explain the ability of multilevel algorithms to produce good partitions. In this paper we present such an analysis. We show under certain reasonable assumptions that even if no refinement is used in the uncoarsening phase, a good bisection of the coarser graph is worse than a good bisection of the finer graph by at most a small factor. We also show that for planar graphs, the size of a good vertex-separator of the coarse graph projected to the finer graph (without performing refinement in the uncoarsening phase) is higher than the size of a good vertex-separator of the finer graph by at most a small factor.

Original languageEnglish (US)
Pages (from-to)658-677
Number of pages20
JournalProceedings of the ACM/IEEE Supercomputing Conference
StatePublished - Dec 1 1995
EventProceedings of the 1995 ACM/IEEE Supercomputing Conference. Part 2 (of 2) - San Diego, CA, USA
Duration: Dec 3 1995Dec 8 1995


Dive into the research topics of 'Analysis of multilevel graph partitioning'. Together they form a unique fingerprint.

Cite this