MASCOTTE no longer exists => visit the new project-team
Internship MASCOTTEReprésentation des graphes d'intervalle
by Jehanne Dousse
| | | | Advisor | F. Havet and D. Mazauric | | School | ENS Lyon | | Degree | Licence | | Period | 01/06/10-16/07/10 |
Un graphe d'intervalle est le graphe d'intersection d'un ensemble d'intervalles de la droite réelle. Plus précisément chaque sommet du graphe d'intervalle représente un intervalle et il y a une arête entre deux sommets du graphe d'intervalle si et seulement si les deux intervalles correspondants s'intersectent. Un graphe d'intervalle est dit unitaire si et seulement si il peut se représenter par des intervalles de même taille. Le problème de decider si un graphe est un graphe d'intervalle unitaire est polynomial. En revanche étant donné un entier k supérieur à 1, nous ne connaissons pas la complexité de décider si un graphe d'intervalle peut se représenter avec des intervalles de k tailles différentes. En d' autres termes pour quelles valeurs de k ce problème est-il NP-complet ? Pour quelles valeurs de k ce problème est-il polynomial ? Après une étude bibliographique, il s'agira d'étudier le problème de décision décrit précédemment en prenant k=2. Il sera possible d'étudier dans un premier temps ce problème de décision avec la contrainte supplémentaire que les deux tailles sont des données du problème. Par exemple, est-ce que décider si un graphe d'intervalle peut se représenter avec des intervalles de taille 1 et des intervalles de taille 2 est polynomial ?
List of interships | 
