Publication: A seed-growth heuristic for graph bisection
Open/View Files
Date
1998
Published Version
Published Version
Journal Title
Journal ISSN
Volume Title
Publisher
The Harvard community has made this article openly available. Please share how this access benefits you.
Citation
Joe 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.
Research Data
Abstract
We 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.
Description
Other Available Sources
Keywords
Terms of Use
This article is made available under the terms and conditions applicable to Other Posted Material (LAA), as set forth at Terms of Service