Share on Facebook Tweet on Twitter Share on LinkedIn Share by email
Exact Combinatorial Branch-and-Bound for Graph Bisection

Daniel Delling, Andrew V. Goldberg, Ilya Razenshteyn, and Renato F. Werneck

Abstract

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.

Details

Publication typeInproceedings
Published inProceedings of the 14th Meeting on Algorithm Engineering and Experiments (ALENEX'12)
PublisherSociety for Industrial and Applied Mathematics
> Publications > Exact Combinatorial Branch-and-Bound for Graph Bisection