Better Bounds for Graph Bisection

Daniel Delling and Renato F. Werneck


We introduce new lower bounds for the minimum graph bisection problem. Within a branch-and-bound framework, they enable the solution of a wide variety of instances with tens of thousands of vertices to optimality. Our algorithm compares favorably with the best previous approaches, solving long-standing open instances in minutes.


Publication typeInproceedings
Published inProceedings of the 20th Annual European Symposium on Algorithms (ESA'12)
SeriesLecture Notes in Computer Science
> Publications > Better Bounds for Graph Bisection