Réduction de l’espace de recherche du Problème de la Somme Coloration Minimum d’un graphe
Le Problème de la Somme Coloration Minimum (MSCP) d’un graphe est un problème d’optimisation combinatoire dont l’objectif est de déterminer une coloration valide minimisant la somme des poids associés aux couleurs utilisées. Le nombre minimum de couleurs dans une solution optimale de MSCP est appelé la force du graphe, et la somme des poids des couleurs utilisées est appelée la somme chromatique du graphe.