Séminaire Mohamed Didi-Biha

Jeudi 11 Mars 2010 (14h00)

Mohamed Didi-Biha, Laboratoire de Mathématiques Nicolas Oresme, CNRS UMR 6139, Université de Caen.

Titre : Etude polyèdrale de quelques problèmes de partionnement dans les graphes.

Résumé : Sous sa forme générale, le problème de partitionnement dans un graphe consiste à partitionner l'ensemble des sommets du graphe en k classes, où k est donné, la cardinalité de chaque classe devant être comprise dans un intervalle donné, tout en minimisant le coût d'une certaine fonction définie sur le graphe. Parfois, on a aussi des contraintes sur la cardinalité de l'ensemble des arêtes entre deux classes de la partition. Ce problème a des applications importantes, entre autres, dans les domaines des télécommunications, du calcul parallèle, des algorithmes du type "divide-and-conquer". Dans cet exposé, nous considérons, d'un point de vue polyèdral, trois cas particuliers de cette classe de problème : le problème de la multicoupe, le problème du séparateur et le problème de la coupe séparatrice.