Reachability in temporal graphs and related problems

Accessibilité dans les graphes temporels et problèmes associés Un graphe temporel est un graphe dont les arêtes changent avec le temps. Ces graphes trouvent des applications dans des domaines très variés tels que l’évolution des épidémies, les réseaux de transports, les réseaux sociaux et les objets mobiles et connectés comme les drones. La théorie des graphes temporels et l’algorithmique dans ces derniers sont en essor depuis un peu plus de vingt ans. Cette thèse est centrée sur les graphes temporels, et plus précisément les problèmes d’accessibilité entre sommets de ces graphes. Un sommet peut joindre un autre sommet via un chemin temporel, aussi appelé trajet, qui emprunte les arêtes en temps croissant. La particularité des graphes temporels, en opposition avec les graphes statiques, est que l’accessibilité entre les sommets n’est pas nécessairement une relation symétrique ni transitive, ce qui génère de nombreuses complications au niveau algorithmique. L’objectif de cette thèse est d’apporter du contenu à l’étude des graphes temporels ainsi que des clarifications, notamment sur les règles de communication entre les sommets via des trajets strict ou non. Cette thèse traite aussi de problèmes liés aux spanneurs, des sous-graphes temporellement connexes dont on cherche à minimiser la taille, qui remplace conceptuellement la notion d’arbre couvrant dans les graphes statiques. La dernière partie de cette thèse établit des liens entre graphes temporels et hérédité dans les graphes statiques, via l’étude de la notion de robustesse de certaines propriétés, ici les distances et le diamètre.