In this paper we present experiments with a class of graph partitioning algorithms that reduce the size of the graph
by collapsing vertices and edges, find a k-way partition of the smaller graph, and then uncoarsen it to construct a
k-way partition for the original graph. These algorithms compute a k-way partition of a graph G D .V ; E/ in O.jEj/
time which is O.log k/ faster than previously proposed multilevel recursive bisection algorithms. We test our scheme
on a large number of graphs arising in various domains including finite element methods, linear programming, VLSI,
and transportation. Our experiments show that our scheme (a) produces partitions that are comparable or even better
to those produced by multilevel recursive bisection algorithms and (b) it is three to five times faster. Our algorithm
compared to multilevel spectral partitioning schemes produces better partitions in substantially smaller time (up to
two orders of magnitude faster).