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.