Aspects algorithmiques et structurels des graphes d'intervalles (multiples)
05/12/2024 à 14h00
Mme Virginia ARDEVOL MARTINEZ présente ses travaux en soutenance le 05/12/2024 à 14h00
À l'adresse suivante : Université Paris Dauphine - PSL Place du Maréchal de Lattre de Tassigny 75016 PARIS -Salle des thèses - D520
En vue de l'obtention du diplôme : Doctorat en Informatique
La soutenance est publique
Titre des travaux
Aspects algorithmiques et structurels des graphes d'intervalles (multiples)
É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)
Monsieur Michail LAMPIS et Monsieur Stéphane VIALETTE
Membres du jury
| Nom | Qualité | Établissement | Rôle |
|---|---|---|---|
| M. Michail LAMPIS | Maître de conférences | UNIVERSITE PARIS DAUPHINE - PSL | Directeur de thèse |
| M. Stéphane VIALETTE | Directeur de recherche | Université Gustave Eiffel | Co-directeur de thèse |
| M. Florian SIKORA | Maître de conférences | UNIVERSITE PARIS DAUPHINE - PSL | Co-encadrant de thèse |
| Mme Marthe BONAMY | Chargé de recherche | Université de Bordeaux | Rapporteure |
| M. Christophe PAUL | Directeur de recherche | Université de Montpellier | Rapporteur |
| Mme Irena RUSU-ROBINI | Professeur des universités | Nantes Université | Examinatrice |
| M. Ioan TODINCA | Professeur des universités | Université d'Orléans | Examinateur |
Résumé
Les graphes d’intervalles multiples sont une généralisation bien connue des graphes d’intervalles, où chaque sommet d’un graphe est représenté par un d-intervalle (l’union de d intervalles) pour un certain nombre naturel d > 1, et il existe une arête entre deux sommets si et seulement si leurs d-intervalles correspondants se croisent. En particulier, un graphe de d-intervalles est unitaire si tous les intervalles de la représentation ont une longueur unitaire. Dans cette thèse, nous étudions les graphes de d-intervalles unitaires d’un point de vue structurel et algorithmique. Dans la première partie, nous essayons de généraliser la caractérisation de Roberts des graphes d’intervalles unitaires, qui affirme qu’un graphe est un graphe d’intervalles unitaire si et seulement s’il est un graphe d’intervalles et ne contient pas le graphe biparti complet K1,3 comme sous-graphe induit. Ensuite, nous passons à l’étude de la complexité de la reconnaissance des graphes d’intervalles multiples unitaires. Nous prouvons que, étant donné un graphe G, il est NP-difficile de déterminer si G est un graphe de d-intervalles unitaires, et nous étendons ensuite ce résultat de difficulté à d’autres sous-classes de graphes de d-intervalles unitaires. Dans la dernière partie de ce manuscrit, nous nous concentrons sur le problème de PIG-completion, qui étant donné un graphe d’intervalles G, demande de trouver le nombre minimum d’arêtes à ajouter à G pour qu’il devienne un graphe d’intervalles unitaire. Nous obtenons un algorithme polynomial lorsque G contient un sommet adjacent à tous les autres sommets du graphe, et un algorithme XP paramétré par une propriété structurelle du graphe.