| In this paper we present and study a class of graph partitioning
algorithms that reduce the size of the graph by collapsing vertices
and edges, find a k-way partitioning of the smaller graph, and then
uncoarsen and refine it to construct a k-way partitioning for the
original graph. These algorithms compute a k-way partitioning of a
graph G=(V,E) in O(|E|) time which is faster by a factor of O(log
k) than previously proposed multilevel recursive bisection algorithms.
A key contribution of our work is in finding a high quality and
computationally inexpensive refinement algorithm that can improve
upon an initial k-way partitioning. We also study the effectiveness
of the overall scheme for a variety of coarsening schemes. We present
experimental results on a large number of graphs arising in various
domains including finite element methods, linear programming, VLSI,
and transportation. Our experiments show that this new scheme
produces partitions that are of comparable or better quality than
those produced by the multilevel bisection algorithm, and requires
substantially smaller time. Graphs containing up to 450000 vertices
and 3300000 edges, can be partitioned in 256 domains in less than
40 seconds on a workstation, such as SGI's Challenge. Compared with
the widely used multilevel spectral bisection algorithm, our new
algorithm is usually two orders of magnitude faster, and produces
partitions with substantially smaller edge-cut.
|