Cette page appartient aux archives web de l'EPFL et n'est plus tenue à jour.
This page belongs to EPFL's web archive and is no longer updated.

Communications ROSO blog

Conférence par VINCENT JOST, ROSO
Mardi 7 novembre 2006
14h15 Salle MA11

Ordonnancement chromatique: polyèdres, complexité et classification.
Résumé:
La coloration des graphes permet de modéliser certaines applications
de la recherche opérationnelle. Souvent, le problème classique de la
coloration minimum n'est pas assez souple pour exprimer les contraintes
qui apparaissent naturellement dans des contextes de plannification
de production, de transport et d'emploi du temps. Or certains des
raffinements nécessaires sont déjà connus dans la théorie de l'ordonnancement.
C'est du mélange de formulations issues de la coloration et de
l'ordonnancement que naît le terme "ordonnancement chromatique".
Par exemple, "l'extension de pré-coloration" consiste à colorier un graphe dans
lequel certains
sommets ont deja une couleur. Nous discutons ensuite "la coloration b-bornée"
dans laquelle
chaque couleur peut être utilisée pour au plus b sommets, (où b est un nombre
entier).
Nous proposons des approches exactes originales pour certains de ces problèmes,
en insistant sur les relations min-max que nous avons obtenus dans des classes
de graphes importantes pour les applications, comme les graphes d'intervalles.
Posted by Thomas Liebling at 9:37