Mazlish, BryanGoodridge, AndrewMarks, Joe2016-02-251994Mazlish, Bryan, Stuart M. Shieber, and Joe Marks. 1994. A Recursive Coalescing Method for Bisecting Graphs. Harvard Computer Science Group Technical Report TR-13-94.http://nrs.harvard.edu/urn-3:HUL.InstRepos:25619462We present an extension to a hybrid graph-bisection algorithm developed by Bui et al. that uses vertex coalescing and the Kernighan-Lin variable-depth algorithm to minimize the size of the cut set. In the original heuristic technique, one iteration of vertex coalescing is used to improve the performance of the original Kernighan-Lin algorithm. We show that by performing vertex coalescing recursively, substantially greater improvements can be achieved for standard random graphs of average degree in the range [2:0; 5:0].en-USnetworks/graphsheuristics: algorithms for graph bisectioncombinatorial optimizationdesign of algorithmsempirical analysis of algorithmsheuristic searchResearch Paper or Report2016-02-25