Improving the Performance of the Kernighan-Lin and Simulated Annealing Graph Bisection Algorithms.

摘要

In this paper, we compare the performance of two popular graph bisection algorithms. We also present an empirical study of a new heuristic, that dramatically improves the performance of these bisection algorithms on graphs with small average degree. In the graph bisection problem we are given a graph G = (V,E) and are asked to partition the vertex set V into two equal-sized subsets V1 and V2 in such a way that the size of the cut between them is minimized. The cut of V1 and V2 is the number of edges with one endpoint in V1 and the other endpoint in V2. The minimum cut over all bisections is known as the bisection width of the graph. Graph bisection has applications in VLSI placement and routing problems. The problem is known to be NP-hard. (kr)