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.

Résumé

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).

Jury

Encadrants

• Directeur de thèse : Miguel Couceiro, UNIVERSITE DE LORRAINE
• Co-directeur de thèse : Victor Lagerkvist, UNIVERSITE DE LINKÖPING

Rapporteurs

• Pierre Charbit, UNIVERSITE PARIS-CITE
• Johanne Cohen, UNIVERSITE PARIS-SACLAY

Examinateurs

• Bernardetta Addis, UNIVERSITE DE LORRAINE
• Jovanka Pantović, FACULTY OF TECHNICAL SCIENCES – SERBIA