The study of dynamic networks has gained increasingly more interest over recent years, motivated mainly by emerging technological contexts like vehicular networks, robots, and drones. Other applications include social networks analysis and influence spreading, and more recently epidemics analysis such as trying to understand the spread of infection (for
example concerning COVID-19). The presence of communication or interaction links in such networks may vary over time due to a variety of reasons, ranging from the removal of physical Ethernet cables and security measures to the effects of social distancing.
Concerning Mobile Ad hoc Networks (MANETs), in which mobile agents are able to communicate when in communication range of each other, controlling mobility of these agents is key for controlling the entirety of the network. Optimal control over a mobile agent’s movements in itself has long been studied in physics and control theory, and has several applications in robotics concerning autonomy and automation, so as to minimize any needed human intervention.
In this thesis, we are interested in several aspects of these topics. More precisely, we consider research questions that pertain respectively to temporal graphs, to mobility, as well as to the interaction between the two. The problem we consider on temporal graphs is motivated by a 20-year old open question, namely what the analog definition of a spanning tree in temporal graphs is. It turns out that this notion has puzzled researchers ever since, due to the fact that even analogs of sparse spanners do not exist in general temporal graphs. Our main result on this topic is showing that sparse spanners however exist in significant particular cases. On the other end of the field of dynamic networks, motivated mostly by the particular case of MANETs, we study the design of physical movements and how this may be approached in an algorithmic fashion, instead of through typical control theory methods. This led us to consider a discrete model of acceleration called racetrack and to revisit the traveling salesperson problem (TSP) with this additional constraint. While seemingly unrelated, the questions of movement design on one hand, and temporal graphs on the other, end up being in strong interaction when considering the execution of distributed algorithms in a MANET scenario. In an effort to connect the two ends of the spectrum, our third contribution considers the interaction between the two, by means of the design of collective movements that induce temporal graph properties in the resulting communication network. This third topic is developed as a software package, available for researchers in distributed computing.