Program > By speacker > Parreau Aline

Wednesday 26
Graphs, flows, combinatorial algorithms and approximation
Alexandre Salch
› 14:20 - 14:40 (20min)
› Bât B - TD 43
Coloration bornée avec multiplicité
Aline Parreau  1, 2@  , François Clautiaux  3  
1 : Département de Mathématique, Université de Liège  -  Website
2 : Laboratoire d'Informatique Fondamentale de Lille  (LIFL)  -  Website
Université Lille III - Sciences humaines et sociales, Université Lille I - Sciences et technologies, CNRS : UMR8022, INRIA
Bâtiment M3 59655 Villeneuve d'Ascq Cédex -  France
3 : RealOpt  (INRIA Bordeaux - Sud-Ouest)
CNRS : UMR0000, Université Victor Segalen - Bordeaux II, Université Sciences et Technologies - Bordeaux I, INRIA, École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB)

 Nous nous intéressons à des graphes avec multiplicités sur les sommets. Ces graphes permettent de modéliser de manière compacte des problèmes dans lesquels il existe des relations entre différentes classes contenant des éléments identiques. En particulier, nous nous intéressons au problème coloration bornée sur ces graphes : comment colorer les sommets du graphe (en donnant autant de couleurs à un sommet que sa multiplicité) de telle sorte que deux sommets adjacents n'aient aucune couleur en commun et que le nombre de sommets d'une même couleur soit borné ?

Ce problème est inspiré du problème de placement unidimensionnel cutting-stock : comment ranger de manière efficace un ensemble d'objets dans des boîtes de taille fixée ? Chaque objet i doit être rangé b(i) fois. Dans cette variante, les objets ont tous la même taille mais certains ne peuvent être rangés ensemble. Il est possible de modéliser ce problème par un problème de coloration bornée sur un graphe où l'on crée pour chaque objet i, b(i) sommets jumeaux. Dans ce cas, le graphe obtenu ne dépend plus polynomialement de la taille de la donnée initiale. Il est donc plus efficace de représenter le nombre d'objets de chaque type par un sommet de multiplicité b(i).

Nous donnons une formulation compacte des solutions de ce problème en utilisant des ensembles stables maximaux. Puis nous montrons que ce problème est NP-complet pour des unions de cliques disjointes mais résolvable en temps polynomial pour les complémentaires de graphes triangulés.


Online user: 2