Nos tutelles

CNRS

Nos partenaires


Accueil > Publications > Thèses > Archives Thèses > Thèses 2014 - 2015

MOMEGE Benjamin


Autour de la connectivité dans les graphes avec conflits.

Jeudi 9 juillet 2015 - 13 h 30 - Amphi Bruno Garcia - Bâtiment ISIMA

Nous nous intéresserons aux graphes avec conflits (un conflit est unepaire d’arêtes ne pouvant pas simultanément faire partie d’un
sous-graphe), dans lesquels nous étudierons différents types de problèmes, de nature aussi bien algorithmique que combinatoire, notre ligne directrice étant la notion de connectivité. Nous verrons que plusieurs résultats, simples sans conflit, ne le sont plus lors de l’ajout de conflits. Nous présenterons : des algorithmes exacts (non polynomiaux), des résultats de NP-complétude, et des conditions suffisantes assurant l’existence de certains objets (arbre couvrant, chemin et cycle Hamiltonien) sans conflits.

Jury :
- M. Pascal Berthomé, Professeur, INSA-CVL, Rapporteur
- M. David Coudert, CR HDR, INRIA, Rapporteur
- M. Mamadou M. Kanté, MCF, UBP, Co-directeur
- M. Christian Laforest, Professeur, UBP, Directeur.