An improved, easily computable combinatorial lower bound for weighted graph bipartitioning

Jesper Larsson Träff, Martin Wimmer

There has recently been much progress on exact algorithms for the (un)weighted graph (bi)partitioning problem using branch-and-bound and related methods. In this note we present an…