A seed-growth heuristic for graph bisection

DSpace/Manakin Repository

A seed-growth heuristic for graph bisection

Citable link to this page


Title: A seed-growth heuristic for graph bisection
Author: Ngo, J. Thomas; Shieber, Stuart ORCID  0000-0002-7733-8195 ; 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:
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
Downloads of this work:

Show full Dublin Core record

This item appears in the following Collection(s)


Search DASH

Advanced Search