A seed-growth heuristic for graph bisection
| Title: | A seed-growth heuristic for graph bisection |
| Author: |
Ngo, J. Thomas; Shieber, Stuart; Ruml, Wheeler; Marks, Joe
Note: Order does not necessarily reflect citation order of authors. |
| 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. |
| Full Text & Related Files: |
Shieber_SeedGrowth.pdf (201.1Kb; PDF) 
|
| 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. |
| Published Version: | http://rtm.science.unitn.it/alex98/book/marks.ps.gz |
| Terms of Use: | This article is made available under the terms and conditions applicable to Other Posted Material, as set forth at http://nrs.harvard.edu/urn-3:HUL.InstRepos:dash.current.terms-of-use#LAA |
| Citable link to this page: | http://nrs.harvard.edu/urn-3:HUL.InstRepos:2260840 |
This item appears in the following Collection(s)
-
FAS Scholarly Articles [5137]
Peer reviewed scholarly articles from the Faculty of Arts and Sciences of Harvard University
Contact administrator regarding this item (to report mistakes or request changes)
