Contributions à la théorie des graphes temporels et aux problèmes de mobilité

Abstract

Dans cette thèse, nous nous intéressons à des questions de recherche qui concernent respectivement les graphes temporels, la mobilité, ainsi que l’interaction entre les deux. Le problème que nous considérons sur les graphes temporels est motivé par une question ouverte depuis 20 ans, à savoir quelle est la définition analogique d’un arbre couvrant dans les graphes temporels. Notre principal résultat dans ce sujet est de montrer que, même si des spanners peu denses n’existent pas dans les graphes temporels en général, ces spanners existent cependant dans des cas particuliers significatifs. À l’autre bout du champ des réseaux dynamiques, nous étudions la conception des mouvements physiques, en considérant un modèle d’accélération discret appelé racetrack dans le contexte du problème du voyageur de commerce (TSP). Les questions de conception de mouvement d’une part, et de graphes temporels d’autre part, sont en forte interaction lorsque l’on considère l’exécution d’algorithmes distribués dans un scénario MANET. Dans ce contexte, la troisième contribution consiste en un progiciel proposant des modèles de mobilité qui induisent des propriétés de graphe temporel dans le réseau de communication résultant.