Abstract
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 language | English (US) |
|---|---|
| Pages (from-to) | 658-677 |
| Number of pages | 20 |
| Journal | Proceedings of the ACM/IEEE Supercomputing Conference |
| Volume | 1 |
| State | Published - Dec 1 1995 |
| Event | Proceedings of the 1995 ACM/IEEE Supercomputing Conference. Part 2 (of 2) - San Diego, CA, USA Duration: Dec 3 1995 → Dec 8 1995 |