Sur les problèmes de graphes sandwichs
Encadrement : Christophe Paul, Michel Habib
Mots clés : Graphes, Algorithmes, Complexité
Le problème et l'état de l'art : Un graphe
sandwich G_s=(V,E_s) est défini par rapport à deux
graphes
G_1=(V,E_1), G_2=(V,E_2) tels que E_1 est inclus dans E_2, et
vérifie
E_1
inclus dans E_s qui est aussi inclus dans E_2. Autrement dit les
arêtes
de E_1 sont "obligatoires" pour G_s et les arêtes de E_2\E_1 sont
optionnelles. Etant donné une propriété Pi, le
problème du Pi-sandwich
consiste à tester étant G_1 et G_2, l'existence d'un
sandwich G_s
vérifiant Pi.
Ce problème peut être vu comme la
généralisation de problèmes classique
de graphes tels que la reconnaissance, la complétion minimale,
la
recherche de sous-graphe maximal pour une propriété Pi...
Etude proposée : Il s'agit d'étendre les
études existantes de 2 manières différentes :
envisager une analyse en complexité paramétrée des
résultats existants et considérer les
problèmes d'optimisation associés.
Travail à réaliser en stage de DEA
1. Etude bibliographique
2. Recherche de critères combinatoire permettant de
paramétrer la
complexité des différents problèmes
étudiés.
3. On pourra s'intéresser à la variante du
problème de sandwich qui consiste à trouver un graphe
sandwich lorsque son existence est garantie.
Ce sujet peut donner lieu à
deux
stages différents (aspects algorithmiques et aspects
complexité). Poursuite en thèse possible.