Title :
Improving the Performance of the Kernighan-Lin and Simulated Annealing Graph Bisection Algorithms
Author :
Bui, Thang ; Jones, Curt ; Heigham, Christopher ; Leighton, Tom
Author_Institution :
Computer Science Department, Pennsylvania State University, University Park, PA
Abstract :
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.
Keywords :
Compaction; Computational modeling; Computer science; Computer simulation; Contracts; Mesh generation; Permission; Simulated annealing; Testing; Very large scale integration;
Conference_Titel :
Design Automation, 1989. 26th Conference on
Print_ISBN :
0-89791-310-8
DOI :
10.1109/DAC.1989.203508
