Cut Size Statistics of Graph Bisection Heuristics

G. R. Schreiber, O. C. Martin

We investigate the statistical properties of cut sizes generated by heuristic algorithms which solve approximately the graph bisection problem. On an ensemble of sparse random grap…