It is shown that Kernighan-Lin and simulated annealing perform better as the average degree of the graph increases. An empirical study of a compaction heuristic that dramatically improves the performance of these bisection algorithms on graphs with a small (≤4) average degree is presented. The performance increase was in both the quality of the solution and the speed in which it was obtained. Kernighan-Lin was found to be a much faster algorithm than simulated annealing on the graphs tested.
All Science Journal Classification (ASJC) codes
- Hardware and Architecture
- Control and Systems Engineering