News - Thesis announce

Date : July 4, 2023, 1:30 p.m. - Timothée MARTINOD - salle A002

Étude de complexité algorithmique pour des problèmes de domination et de tournées dans les graphes avec obligation

Des capteurs, des machines, des équipes peuvent être interdépendantes, nécessitant une mobilisation collective. Elles ne peuvent accomplir leurs missions individuellement. Nous représentons cette contrainte par une obligation et nous y intéressons d'un point de vue théorique à travers des problèmes de graphes. Nous distinguons deux types d'obligations : les obligations associées à plusieurs sommets et les transitions obligatoires associées à plusieurs arcs. Ainsi, nous étudions la complexité de deux familles de problèmes : les problèmes de domination avec obligations et les problèmes de tournées avec transitions obligatoires. La plupart des résultats que nous montrons sont des résultats de NP-complétude et de non-approximation, dans des topologies de graphes restreintes.

Composition du jury :
Rodolphe Giroudeau, Maître de conférences, Université de Montpellier - Rapporteur
Johanne Cohen, Directrice de recherche CNRS, Université Paris-Saclay - Rapporteure
Sylvie Norre, Professeure des universités, Université Clermont Auvergne - Examinatrice
Christian Laforest, Professeur des universités, Université Clermont Auvergne - Directeur de thèse.