Affordable Access

Problème de la bipartition minimale d'un graphe

Authors
Publication Date
Disciplines
  • Computer Science
  • Mathematics

Abstract

Problème de la bipartition minimale d'un graphe REVUE FRANÇAISE D’AUTOMATIQUE, D’INFORMATIQUE ET DE RECHERCHE OPÉRATIONNELLE. RECHERCHE OPÉRATIONNELLE CATHERINEROUCAIROL PIERREHANSEN Problème de la bipartitionminimale d’un graphe Revue française d’automatique, d’informatique et de recherche opérationnelle. Recherche opérationnelle, tome 21, no 4 (1987), p. 325-348. <http://www.numdam.org/item?id=RO_1987__21_4_325_0> © AFCET, 1987, tous droits réservés. L’accès aux archives de la revue « Revue française d’automatique, d’infor- matique et de recherche opérationnelle. Recherche opérationnelle » implique l’accord avec les conditions générales d’utilisation (http://www.numdam.org/ legal.php). Toute utilisation commerciale ou impression systématique est constitutive d’une infraction pénale. Toute copie ou impression de ce fi- chier doit contenir la présente mention de copyright. Article numérisé dans le cadre du programme Numérisation de documents anciens mathématiques http://www.numdam.org/ R.A.I.R.O. Recherche opérationnelle/Opérations Research (vol. 21, n° 4, novembre 1987, p. 325 à 348) PROBLÈME DE LA BIPARTITION MINIMALE D'UN GRAPHE (*) par Catherine ROUCAIROL (*) et Pierre HANSEN (2) Résumé. — Le problème posé consiste à chercher une partition d'un graphe value en deux parties de taille fixée de façon à minimiser la somme des coûts des arcs « à cheval » (ayant une extrémité dans chacune des parties). Après avoir formulé ce problème comme un programme quadratique en variables 0,1 SOMS contrainte, nous montrons comment calculer une borne inférieure par relaxation lagrangienne; le multiplicateur de Lagrange optimal est trouvé en, au plus, (n — 1) applications d'un algorithme de flot maximal dans un réseau à n + 2 sommets et n + m arcs, n nombre de sommets et m d'arcs du graphe initial. Cette borne est utilisée dans un algorithme « Branch and Bound ». Les résultats obtenus montrent que cet algorithme fournit une solution optimale en des temps raisonnables, très infé

There are no comments yet on this publication. Be the first to share your thoughts.