Ordonnancement chromatique (polyèdres, complexité et classification)

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 les applications. Certains des raffinements nécessaires sont déjà connus dans la théorie de l'ordonnancement. Cela mène à des formulations hybrides regroupées sous le terme "ordonnancement chromatique". Ces contraintes mènent à des problèmes comme la coloration bornée , l'extension pré-colorée ou la max-coloration . Nous construisons de nouvelles bornes inférieures pour la valeur optimum de ces problèmes de minimisation. Les résultats principaux montrent que ces bornes inférieures donnent des formules min-max et mènent à des algorithmes efficaces dans des sous-classes de graphes parfaits. C'est en particulier le cas pour les compléments de graphes d'intervalles (fondamentaux dans les problèmes de production et de transport) ou les line-graphes de bipartis (fondamentaux dans les problèmes d'emploi du temps). Ces problèmes d'ordonnancement chromatique sont souvent NP-difficiles même dans les graphes bipartis (et donc dans les graphes parfaits). En fonction du problème et de la classe de graphe à laquelle on s'intéresse, nous avons tenté de tracer les frontières entre les cas polynomiaux, les cas NP-difficiles et les cas où la borne inférieure proposée donne une formule min-max. Ceci permet de résumer les principaux résultats connus et d'orienter les recherches pour trouver des bornes inférieures plus générales ainsi que des algorithmes ayant un bon rapport d'approximation.GRENOBLE1-BU Sciences (384212103) / SudocSudocFranceF