Retour à l'index du GREYC

Séminaire Algorithmique

Site du CNRS

Séminaire Algorithmique

Le séminaire a lieu le mardi à 11 h 45 (sauf modification exceptionnelle), au campus Côte de Nacre, bâtiment Sciences 3, salle S3 351, 3ème étage.

Résumé du séminaire du Mardi 19 Avril 2011

Étude polyédrale de quelques problèmes de partionnement dans les graphes

par Mohamed Didi Biha (LMNO, Caen)

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èmes : le problème de la multicoupe, le problème du séparateur et le problème de la coupe séparatrice.

GREYC
Campus Côte de Nacre, boulevard du Maréchal Juin
BP 5186
14032 Caen Cedex
FAX : +33 (0)2 31 56 73 30
http://www.greyc.fr