Groupe d’études et de recherche en analyse des décisions

G-2014-25

A comparison of integer and constraint programming models for the deficiency problem

, et

Une coloration des arêtes d'un graphe \(G\) est une fonction qui attribue un entier (appelé couleur) à chaque arête de \(G\) de telle sorte que les arêtes adjacentes aient des couleurs différentes. Une coloration des arêtes est compacte si les couleurs incidentes à chaque sommet forment un intervalle d'entiers consécutifs. Le problème de la déficience consiste à déterminer le nombre minimum d'arêtes pendantes qui doivent être rajoutées de telle sorte que le graphe résultant admette une coloration compacte de ses arêtes. Nous proposons et analysons trois modèles de programmation mathématique en nombres entiers et un modèle de programmation par contraintes pour le problème de la déficience.

, 16 pages