Problème de la bipartition minimale d’un graphe. (The minimal bipartitioning problem of a graph). (French) Zbl 0628.90049

Roucairol, Catherine; Hansen, Pierre

RAIRO, Rech. Opér. 21, 325-348 (1987).

The problem considered is that of partitioning an arc-weighted graph into two parts, each of which constrained in size, in order to minimize the sum of the costs of the cut arcs. After formulating this problem as a 0-1 quadratic program, we calculated a lower bound by using Lagrangian relaxation. The best Lagrangian multiplier is determined in at most (n-1) applications of a maximum flow algorithm to a network with \(n+2\) vertices and \(n+m\) arcs, where n and m denote the number of vertices and arcs in the initial graph. A branch-and-bound algorithm using this result is presented and computational experience shows that an optimal solution is obtained within quite reasonable times which are much less than for the exact methods known up to now.

MSC:

90C09	Boolean programming
05C70	Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.)
90B10	Deterministic network models in operations research
90C20	Quadratic programming
90C35	Programming involving graphs or networks
90C10	Integer programming
65K05	Numerical mathematical programming methods

Keywords:

minimal bipartitioning; minimal cut; arc-weighted graph; lower bound; Lagrangian relaxation; maximum flow; branch-and-bound