A Seed-Growth Heuristic for Graph Bisection

We present a new heuristic algorithm for graph bisection, based on an implicit notion of clustering. 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 comparisons with large-sample runs of pure Kernighan-Lin, the new algorithm demonstrates significant superiority in terms of the best bisections found. 1 Introduction Given a graph G = (V; E) with an even number of vertices, the graph-bisection problem is to divide V into two equal-size subsets X and Y such that the number of edges connecting vertices in X to vertices in Y (the size of the cut set , notated cut(X; Y )) is minimized. This problem is NP-complete [7]. Graph bisection and its generalizations 1 have considerable practical significance, especially in the areas of VLSI design and operations research. The benchmark algorithm for graph bisection is due to Kernighan and Lin [13]. (The efficient implementation..