We present a novel exact algorithm for the minimum graph bisection problem, whose goal is to partition a graph into two equally-sized cells while minimizing the number of edges between them. Our algorithm is based on the branch-and-bound framework and, unlike most previous approaches, it is fully combinatorial. We present stronger lower bounds, improved branching rules, and a new decomposition technique that contracts entire regions of the graph without losing optimality guarantees. In practice, our algorithm works particularly well on instances with relatively small minimum bisections, solving large real-world graphs (with tens of thousands to millions of vertices) to optimality.

}, author = {Daniel Delling and Andrew V. Goldberg and Ilya Razenshteyn and Renato F. Werneck}, booktitle = {Proceedings of the 14th Meeting on Algorithm Engineering and Experiments (ALENEX'12)}, publisher = {Society for Industrial and Applied Mathematics}, title = {Exact Combinatorial Branch-and-Bound for Graph Bisection}, url = {http://research.microsoft.com/apps/pubs/default.aspx?id=156566}, year = {2012}, }