Actualité - Annonce de Thèse

Date : 2 septembre 2020 09:00 - Oscar DEFRAIN - Amphi recherche pôle physique

Sur le problème de dualisation dans les graphes, hypergraphes, et treillis
Cette thèse s'inscrit en informatique et en algorithmique d'énumération.
Nous nous intéressons à la complexité du problème de dualisation 
des fonctions monotones Booléennes à travers les différentes formes 
qu'il prend dans les graphes, hypergraphes, et treillis.
Tout particulièrement dans cet exposé, nous nous intéresserons à l'énumération 
des dominants minimaux dans les graphes, et présenterons de nouveaux algorithmes 
output-polynomiaux pour résoudre le problème dans les graphes sans grande clique, 
ainsi que dans quelques autres classes de graphes liées.
Dans une seconde partie, nous nous intéresserons à une généralisation naturelle 
du problème dans les treillis, et passerons en revue les dernières 
avancées sur ce problème.
La présentation se terminera par les perspectives futures autour 
de la dualisation dans ces structures.

Accès:
http://www.recherche-environnement.univ-bpclermont.fr/wp/wp-content/uploads/2015/11/cezeaux-pole-physique.png


Jury :
Nadia CREIGNOU (Pr, Université Aix Marseille) rapporteur
Sergei KUZNETSOV (Pr, Higher School of Economics, Moscow) rapporteur 
Kazuhisa MAKINO (Pr, Reasearch Institute of Math. Sciences, Kyoto) rapporteur
Victor CHEPOI (Pr, Université Aix Marseille) examinateur
Arnaud DURAND (Pr, Université Paris Diderot) examinateur
Aurélie LAGOUTTE (MCF, UCA) examinatrice
Lhouari NOURINE (Pr, UCA) directeur de thèse.