Ambroise Baril (Orpailleur) soutiendra sa thèse intitulée “Complexité fine et paramétrée des problèmes de coloriage de graphe” le 24 juin à 10h en salle A008.
L’objectif de la thèse est d’étudier la complexité fine et paramétrée du problème de H-coloration, ainsi que la classe plus générale des problèmes CSP(Gamma), en utilisant des méthodes d’algèbre universelle. Ici, l’approche récemment développée basée sur la théorie des clones partiels semble être pertinente, puisqu’on sait que les polymorphismes partiels (pPol(·)) des langages de contraintes sont corrélés à la complexité de CSP(Gamma) dans le pire cas le pire des cas O(c^n).
Encadrants
Rapporteurs
Examinateurs
