Date : Sept. 11, 2023, 1:30 p.m. - Caroline BROSSE - Salle A102
Efficient enumeration algorithms for minimal graph completions and deletions
This thesis is about graph theory and more specifically enumeration algorithms for subgraphs or supergraphs. The problem we consider is the following: given a graph G and a graph property P, can we find an efficient algorithm generating exactly once all the inclusion-wise maximal (induced or not) subgraphs of G that satisfy the property P? We are interested as well in inclusion-wise minimal supergraphs of G - called minimal completions of G - verifying P.
Efficient algorithms, running with polynomial delay in polynomial space, are obtained for some of these problems when P describes the classes of split graphs, cographs, threshold graphs and chordal graphs.
Fatiha Bendali - Université Clermont Auvergne - Examiner
Marthe Bonamy - CNRS, Université de Bordeaux - Examiner
Nofar Carmeli - Inria, Université de Montpellier - Examiner
Roberto Grossi - Università di Pisa - Referee
Christian Laforest - Université Clermont Auvergne - Examiner
Vincent Limouzy - Université Clermont Auvergne - Supervisor
Ioan Todinca - Université d'Orléans - Referee
Nicolas Trotignon - CNRS, ENS de Lyon - Examine.