Contribution à la résolution des problèmes de la coloration et la somme coloration de graphes

Abstract

Le problème de la coloration de graphe (GCP) est un problème classique de l’optimisation combinatoire appartenant à la classe des problèmes NP-difficiles avec des applications réelles dans nombreux domaines de l’ingénierie, incluant l’ordonnancement, l’emploi du temps, l’allocation de registres, l’assignation de fréquence, et les réseaux de communication, etc. Nous proposons une étude pour la résolution de (GCP) par deux métaheuristiques à base de population en faisant une comparaison des valeurs approchées du nombre chromatique χ(G) et le temps d’exécution pour les deux métaheuristiques. Nous présentons ensuite, une application d’un nouveau schéma stéganographique pour les images gray-scale utilisant la coloration de graphe. Nos travaux étaient plus concentrés sur le problème de la somme coloration minimale (MSCP) qui consiste à trouver une coloration des sommets d’un graphe, utilisant des entiers naturels, telle que la somme des couleurs soit minimale. MSCP est connu pour être NP-difficile dans le cas général. En plus de son importance théorique comme un problème combinatoire difficile, MSCP se distingue par le grand nombre de problèmes NP-complet qui peuvent être modélisés sous la forme de MSCP, par exemple: le problème de la conception VLSI, le problème d’ordonnancement et le problème d’allocation des ressources. Nous présentons dans le chapitre 4 une synthèse des travaux portés sur MSCP, nous proposons par la suite différentes nouvelles approches afin de générer de meilleures bornes pour MSCP. L’ensemble des tests numériques ont été menés pour diverses instances et montrent que nos approches améliorent les bornes inférieures et supérieures de la littérature.