Improving the performance of the Kernighan-Lin and simulated annealing graph bisection algorithms
T. Bui, C. Heigham, Curt Jones, T. Leighton · 1989
In this paper, we compare the performance of two popular graph bisection algorithms. We also present an empirical study of a new heuristic, first proposed in [B87], that dramatically improves the performance of these bisection algorithms on graphs with small (≤ 4) average degree.