A seed-growth heuristic for graph bisection
Ngo, J. Thomas
MetadataShow full item record
CitationJoe Marks, Wheeler Ruml, Stuart M. Shieber, and Tom Ngo. A seed-growth heuristic for graph bisection. In R. Battiti and A. A. Bertossi, editors, Proceedings of Algorithms and Experiments '98, pages 76-87, Trento, Italy, February 9-11 1998.
AbstractWe present a new heuristic algorithm for graph bisection, based on an implicit notion of clustering. We describe how the heuristic can be combined with stochastic search procedures and a postprocess application of the Kernighan-Lin algorithm. In a series of time-equated comparisons with large-sample runs of pure Kernighan-Lin, the new algorithm demonstrates significant superiority in terms of the best bisections found.
Citable link to this pagehttp://nrs.harvard.edu/urn-3:HUL.InstRepos:2260840
- FAS Scholarly Articles