L'étude des réseaux dynamiques a suscité un intérêt croissant au cours des dernières années, motivée principalement par les contextes technologiques émergents tels que les réseaux de véhicules, les robots et les drones. Parmi les autres applications figurent l'analyse des réseaux sociaux et la diffusion d'influences, et plus récemment, l'analyse des épidémies, afin de comprendre la propagation de l'infection (par exemple concernant COVID-19). La présence de liens de communication ou d'interaction dans ces réseaux peut varier dans le temps pour diverses raisons, allant de la suppression de câbles Ethernet physiques et de mesures de sécurité, aux effets de la distanciation sociale.
En ce qui concerne les réseaux mobiles ad hoc (MANET), dans lesquels des agents mobiles sont capables de communiquer lorsqu'ils sont à proximité les uns des autres, la maîtrise de la mobilité de ces agents est essentielle pour contrôler l'ensemble du réseau. Le contrôle optimal des mouvements d'un agent mobile en soi est étudié depuis longtemps en physique et dans la théorie du contrôle, et présente plusieurs applications en robotique concernant l'autonomie et l'automatisation, de manière à minimiser toute intervention humaine nécessaire.
Dans cette thèse, nous nous intéressons à plusieurs aspects de ces sujets. Plus précisément, nous nous concentrons sur des questions de recherche qui se rapportent respectivement aux graphes temporels, à la mobilité, ainsi qu'à l'interaction entre les deux. Le problème que nous examinons sur les graphiques temporels est motivé par une question ouverte vieille de vingt ans, concernant une définition analogue à celle de l'arbre couvrant pour les graphes temporels. Il s'avère que cette notion a toujours intrigué les chercheurs depuis, du fait même que les analogues de spanners peu denses n'existent pas dans les graphes temporels dans le cas général. Notre principal résultat sur ce sujet est de montrer que les spanners peu denses existent cependant dans des cas particuliers significatifs. À l'autre extrémité du domaine des réseaux dynamiques, motivés principalement par le cas particulier des MANET, nous étudions la conception des mouvements physiques et la façon dont elle peut être abordée de manière algorithmique, au lieu de recourir aux méthodes typiques de la théorie du contrôle. Cela nous conduit à envisager un modèle discret d'accélération appelé "racetrack" et à réexaminer le problème du voyageur de commerce (TSP) avec cette contrainte supplémentaire. Bien qu'elles semblent sans rapport, les questions de la conception de mouvements d'une part, et des graphes temporels d'autre part, finissent par être en forte interaction lorsqu'on envisage l'exécution d'algorithmes distribués dans un scénario MANET. Dans le but de relier les deux extrémités du spectre, notre troisième contribution examine l'interaction entre les deux, au moyen de la conception de mouvements collectifs induisant des propriétés de graphes dans le réseau de communication qui en résulte. Ce troisième sujet est développé comme une bibliothèque de fonctionnalités, disponible pour les chercheurs en algorithmique distribuée.