and

We present a new heuristic algorithm for graph bisection, based on an implicit notion of clus-tering. We describe how the heuristic can be combined with stochastic search procedures and a postprocess application of the Kernighan-Lin algorithm. In a series of time-equated compar-isons with large-sample runs of pure Kernighan-Lin, the new algorithm demonstrates signicant superiority in terms of the best bisections found.