Algorithmes et Intractabilité de Certains Problèmes de Domination NP-difficiles avec Structure Privée
01/07/2021 à 14h00
M. Louis DUBLOIS présente ses travaux en soutenance le 01/07/2021 à 14h00
À l'adresse suivante : En visio conférence
En vue de l'obtention du diplôme : Doctorat en Informatique
La soutenance est publique
Titre des travaux
Algorithmes et Intractabilité de Certains Problèmes de Domination NP-difficiles avec Structure Privée
École doctorale
École doctorale Dauphine SDOSE
Équipe de recherche
UMR 7243 - Laboratoire d’Analyse et de Modélisation de Systèmes d’Aide à la Décision
Section CNU
27 - Informatique
Directeur(s)
M. Vangelis PASCHOS
Membres du jury
| Nom | Qualité | Établissement | Rôle |
|---|---|---|---|
| M. Vangelis PASCHOS | Professeur | UNIVERSITE PARIS DAUPHINE - PS | M. Vangelis PASCHOS Professeur UNIVERSITE PARIS DAUPHINE - PSL Directeur de thèse |
| M. Bruno ESCOFFIER | Professeur | Sorbonne Université | Rapporteur |
| M. Cédric BENTZ | Maître de conférences | Conservatoire National des Arts et Métier | Rapporteur |
| Mme Valia MITSOU | Maître de conférences | Université de Paris | Examinatrice |
| M. Christophe PICOULEAU | Professeur | Conservatoire National des Arts et Métiers | Examinateur |
| M. Michael LAMPIS | Maître de conférences | UNIVERSITE PARIS DAUPHINE - PSL | Examinateur |
Résumé
Pour résoudre des problèmes NP-difficiles, plusieurs paradigmes ont été développés durant les dernières décennies : l'approximation polynomiale, la résolution exacte, ou encore l'approximation super-polynomiale. Aussi, il a été prouvé que sous certaines hypothèses de complexité, il est impossible d'obtenir certains algorithmes. Dans cette thèse, nous présentons certaines méthodes permettant d'obtenir des algorithmes dans ces différents paradigmes, ainsi que des méthodes pour obtenir des résultats d'impossibilité. Nous illustrons ces méthodes en les mettant en oeuvre sur trois problèmes de domination NP-difficiles qui possèdent une structure privée: Min Mixed Dominating Set, où l'on cherche un ensemble minimum d'arêtes et de sommets qui dominent toutes les arêtes et sommets du graphe ; Max Min Feedback Vertex Set, où l'on cherche un feedback vertex set minimal de taille maximum ; et Upper Dominating Set, où l'on cherche un dominating set minimal de taille maximum.