Issue |
RAIRO-Oper. Res.
Volume 35, Number 4, October December 2001
|
|
---|---|---|
Page(s) | 401 - 414 | |
DOI | https://doi.org/10.1051/ro:2001122 | |
Published online | 15 August 2002 |
Un Algorithme pour la Bipartition d'un Graphe en Sous-graphes de Cardinalité Fixée
1
Laboratoire d'Informatique d'Avignon, UAPV,
BP. 1228, 84911 Avignon Cedex 9, France.
2
Université de Montréal, DIRO, CP. 6128, Succursale
Centre-Ville, Montréal (Québec) H3C 3J7 Canada.
3
Universidade Federal do Rio de Janeiro, COPPE/Sistemas, P.O.
Box 68511, Rio de Janeiro, RJ 21945–790, Brésil.
Received:
December
1998
A branch-and-bound method for solving the min cut with size constraint problem is presented. At each node of the branch-and-bound tree the feasible set is approximated by an ellipsoid and a lower bound is computed by minimizing the quadratic objective function over this ellipsoid. An upper bound is also obtained by a Tabu search method. Numerical results will be presented.
Résumé
Nous présentons une méthode de Séparation et Évaluation Progressive pour la bipartition d'un graphe en 2 sous-ensembles ayant une cardinalité fixée. À chaque nœud de l'arbre de recherche, nous calculons une borne inférieure en dualisant les contraintes d'intégralité et en approximant le domaine réalisable par un ellipsoïde. Une borne supérieure est également calculée par la méthode Tabou. Des résultats numériques sont présentés et commentés.
© EDP Sciences, 2001
Current usage metrics show cumulative count of Article Views (full-text article views including HTML views, PDF and ePub downloads, according to the available data) and Abstracts Views on Vision4Press platform.
Data correspond to usage on the plateform after 2015. The current usage metrics is available 48-96 hours after online publication and is updated daily on week days.
Initial download of the metrics may take a while.