Share on Facebook Tweet on Twitter Share on LinkedIn Share by email
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