Antoine Toullalan soutiendra sa thèse intitulée « Problèmes d'exploration dans les graphes temporels ».
Date : Vendredi 5 novembre à 13h30
Lieu : Amphithéâtre Normand, UFR Sciences et Techniques, site Lebon, Université du Havre.
Lien visio : https://visio.numerique.gouv.fr/est-sbwh-eto
Le jury de thèse sera composé de :
Éric Sanlaville - Université Le Havre Normandie (Directeur de thèse)
Stefan Balev - Université Le Havre Normandie (Co-encadrant)
Thomas Erlebach - Université de Durham (Examinateur)
Binh-Minh Bui-xuan - Sorbonne Université, CNRS (Rapporteur du jury)
Arnaud casteigts - Université de Genève (Rapporteur du jury)
Mathilde Vernet - Université d'Avignon (Examinatrice)
Laurent Viennot - INRIA Paris (Examinateur)
Un pot de thèse sera organisé après la soutenance dans la salle de pause du LITIS en B101, où vous êtes tous chaleureusement invités.
Vous trouverez ci-dessous le résumé de ma thèse :
Les graphes temporels permettent de modéliser des réseaux dynamiques en associant à chaque arête des pas de temps de présence. Un des problèmes les plus étudié dans les graphes temporels est le problème de l'exploration qui cherche un trajet qui visite tout les sommets. Dans le cas statique, l'unique critère minimisé est le nombre d'arêtes traversées mais dans le cas temporel, trois critères peuvent être minimisé: le temps d'arrivée du trajet, le nombre de pas de temps entre le départ et l'arrivée, et le nombre d'arêtes traversées.
L'objectif de cette thèse est d'étudier les graphes temporels connexes à chaque pas de temps à travers le problème de l'exploration minimisant le temps d'arrivée et le nombre d'arêtes traversées.
Premièrement, nous nous intéressons au cas de l'exploration minimisant uniquement le temps d'arrivée : pour des classes de graphes temporels constamment connexes avec des contraintes sur l'ensemble d'arêtes présents à chaque pas de temps, nous prouvons l'existence de trajets d'exploration avec des bornes supérieure sur le temps d'arrivée. Dans le deuxième cas, nous prouvons l'existence d'un trajet d'exploration en $O(|V|^2)$ pas de temps ($V$ est l'ensemble de sommets) avec une borne supérieure sur le nombre d'arêtes traversées dans les graphes constamment connexes.
L'étude du problème de l'exploration dans le deuxième cas nous a amenés à étudier les conditions suffisantes pour les trajets dans les graphes temporels traversant un nombre d'arêtes bornés.