Seed-Growth Heuristics for Graph Bisection

DSpace/Manakin Repository

Seed-Growth Heuristics for Graph Bisection

Citable link to this page


Title: Seed-Growth Heuristics for Graph Bisection
Author: Ruml, Wheeler; Marks, Joe; Shieber, Stuart Merrill ORCID  0000-0002-7733-8195 ; Ngo, J. Thomas

Note: Order does not necessarily reflect citation order of authors.

Citation: Ruml, Wheeler, Joe Marks, Stuart M. Shieber, and J. Thomas Ngo. 1999. Seed-Growth Heuristics for Graph Bisection. Harvard Computer Science Group Technical Report TR-10-99.
Full Text & Related Files:
Abstract: We investigate a family of algorithms for graph bisection that are based on a simple local connectivity heuristic, which we call seed-growth. We show 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 against large-sample runs of pure Kernighan-Lin, the new algorithms find bisections of the same or superior quality. Their performance is particularly good on structured graphs representing important industrial applications. An appendix provides further favorable comparisons to other published results. Our experimental methodology and extensive empirical results provide a solid foundation for further empirical investigation of graph-bisection algorithms.
Terms of Use: This article is made available under the terms and conditions applicable to Other Posted Material, as set forth at
Citable link to this page:
Downloads of this work:

Show full Dublin Core record

This item appears in the following Collection(s)


Search DASH

Advanced Search