Coloration bornée avec multiplicité
PARREAU, Aline
Département de Mathématiques [Liège]
Laboratoire d'Informatique Fondamentale de Lille [LIFL]
Département de Mathématiques [Liège]
Laboratoire d'Informatique Fondamentale de Lille [LIFL]
PARREAU, Aline
Département de Mathématiques [Liège]
Laboratoire d'Informatique Fondamentale de Lille [LIFL]
< Reduce
Département de Mathématiques [Liège]
Laboratoire d'Informatique Fondamentale de Lille [LIFL]
Language
fr
Communication dans un congrès
This item was published in
ROADEF - 15ème congrès annuel de la Société française de recherche opérationnelle et d'aide à la décision, 2014-02-26, Bordeaux.
Abstract
<p> 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 ...Read more >
<p> 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é ?</p> <p>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).</p> <p>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.</p>Read less <
English Keywords
graphe
coloration
multiplicité
packing
cutting stock
Origin
Hal imported