News - Thesis announce

Date : Sept. 2, 2020, 9 a.m. - DEFRAIN Oscar - Amphi recherche pôle physique

On the dualization problem in graphs, hypergraphs, and lattices
This thesis deals with enumeration problems and algorithms.
We are interested in the complexity of the dualization of monotone Boolean functions through the different shapes it takes in graphs, hypergraphs, and lattices. In particular in this talk, we will consider the enumeration of minimal dominating sets in graphs, and will present new output-polynomial time algorithms to solve the problem in graphs without large cliques, as well as in some other related graph classes. In a second part, we will consider a natural generalization of this problem in lattices, and will review the recent progress on the problem. The presentation will end with different perspectives on the dualization problem in these structures. Access:

Nadia CREIGNOU (Pr, Université Aix Marseille) reviewer
Sergei KUZNETSOV (Pr, Higher School of Economics, Moscow) reviewer 
Kazuhisa MAKINO (Pr, Reasearch Institute of Math. Sciences, Kyoto) reviewer
Victor CHEPOI (Pr, Université Aix Marseille) examiner
Arnaud DURAND (Pr, Université Paris Diderot) examiner
Aurélie LAGOUTTE (MCF, UCA) examiner
Lhouari NOURINE (Pr, UCA) supervisor