Share on Facebook Tweet on Twitter Share on LinkedIn Share by email
Better Bounds for Graph Bisection

Daniel Delling and Renato Werneck

Abstract

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.

Details

Publication typeTechReport
NumberMSR-TR-2012-69
PublisherMicrosoft Technical Report
> Publications > Better Bounds for Graph Bisection