Bipartition of a graph with minimal cost

Bipartition of a graph with minimal cost

0.00 Avg rating0 Votes
Article ID: iaor1988201
Country: France
Volume: 21
Issue: 4
Start Page Number: 328
End Page Number: 348
Publication Date: Nov 1987
Journal: RAIRO Operations Research
Authors: ,
Abstract:

The problem considered is that of partitioning a 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 guadratic program, the authors 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.

Reviews

Required fields are marked *. Your email address will not be published.