1. A Recursive Coalescing Method for Bisecting Graphs
- Author
-
Mazlish, Bryan, Shieber, Stuart Merrill, and Marks, Joe
- Subjects
networks/graphs ,heuristics: algorithms for graph bisection ,combinatorial optimization ,design of algorithms ,empirical analysis of algorithms ,heuristic search - Abstract
We present an extension to a hybrid graph-bisection algorithm developed by Bui et al. that uses vertex coalescing and the Kernighan-Lin variable-depth algorithm to minimize the size of the cut set. In the original heuristic technique, one iteration of vertex coalescing is used to improve the performance of the original Kernighan-Lin algorithm. We show that by performing vertex coalescing recursively, substantially greater improvements can be achieved for standard random graphs of average degree in the range [2:0; 5:0]., Engineering and Applied Sciences
- Published
- 1994