Partial Independant Dominant with Obligations in graph ,
Etude de graphe - Projet étudiant

Le problème des ensembles dominants indépendants avec obligations est une variante du problème classique des ensembles indépendants dominants minimums.
On considère G, un graphe non orienté, et O, appelé ensemble d'obligation, un partitionnement stable de l'ensemble des sommets de G. On cherche à savoir si il existe un ensemble indépendant dominant E (cad tous sommets de G est inclu dans E ou voisin d'au moins un sommet de E) respectant les obligations (cad si un sommet est inclu dans E, tous les sommets de son obligation le sont aussi). Ce problème est NP complet.
Ce projet a été réalisé en binôme, sous la tutelle de C. Laforest, dans le cadre du projet final de prep'isima II.
L'idée a été de proposer des algorithmes de résolution partielle et de les évaluer, en générant des instances et en créant des outils d'évaluation et de visualisation statistique.