Abstract
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.
| Original language | English (US) |
|---|---|
| Pages (from-to) | 775-778 |
| Number of pages | 4 |
| Journal | Proceedings - Design Automation Conference |
| DOIs | |
| State | Published - 1989 |
| Event | 26th ACM/IEEE Design Automation Conference - Las Vegas, NV, USA Duration: Jun 25 1989 → Jun 29 1989 |
All Science Journal Classification (ASJC) codes
- Hardware and Architecture
- Control and Systems Engineering