Exact Combinatorial Branch-and-Bound for Graph Bisection

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.

bisection_alenex.pdf
PDF file

In  Proceedings of the 14th Meeting on Algorithm Engineering and Experiments (ALENEX'12)

Publisher  Society for Industrial and Applied Mathematics

Details

TypeInproceedings
> Publications > Exact Combinatorial Branch-and-Bound for Graph Bisection