TR94-18

A Stochastic Search Technique for Graph Bisection

    •  Joe Marks, Stuart Shieber, J. Thomas Ngo, "A Stochastic Search Technique for Graph Bisection", Tech. Rep. TR94-18, Mitsubishi Electric Research Laboratories, Cambridge, MA, November 1994.
      BibTeX TR94-18 PDF
      • @techreport{MERL_TR94-18,
      • author = {Joe Marks, Stuart Shieber, J. Thomas Ngo},
      • title = {A Stochastic Search Technique for Graph Bisection},
      • institution = {MERL - Mitsubishi Electric Research Laboratories},
      • address = {Cambridge, MA 02139},
      • number = {TR94-18},
      • month = nov,
      • year = 1994,
      • url = {https://www.merl.com/publications/TR94-18/}
      • }
Abstract:

We present a new heuristic algorithm for graph bisection. This heuristic combines stochastic search and an implicit notion of clustering in a novel manner. In comparison with a large-sample, time-equated set of runs of the Kernighan-Lin algorithm, the new algorithm demonstrates a modest but significant superiority in terms of the best bisections found. Keywords and phrases: graph bisection, graph partitioning, stochastic search, heuristics.