“I think temporal graphs are important as they can find application in a huge variety of domains, since many networks have inherent dynamic behavior.” Filippo Brunelli, former PhD student at IRIF.
Link to his PhD thesis: Algorithmic aspects of reachability in temporal graphs (His thesis has not yet been published by the university; the data will be updated as soon as it is).

I am Filippo Brunelli, and I recently completed my PhD studies in theoretical computer science, obtaining my diploma from Université Paris Cité. I was enrolled as a PhD student at Inria, but I conducted most of my research at Irif, where I was hosted. Before moving to Paris, I completed my university studies in Italy. I first obtained a bachelor's degree in mathematics at the University of Trento, then a master's degree in mathematics at the University of Pisa.

I first learned about graphs during an algorithm course in my bachelor studies. I became fascinated with the subject and focused my bachelor's thesis on a related topic: the price of anarchy and selfish routing in graphs. When I chose to pursue my master studies in Pisa I made sure to be able to follow courses involving graphs and algorithms, like operations research and network optimization. For my master's thesis I started to work for the first time on temporal graphs, which then became the central topic of my PhD studies.

My thesis revolves around temporal graphs. I studied different models of them and mostly focused on problems that can be applied to the field of transport networks, for example the counterpart in temporal graphs of the classical shortest path problem studied in graph theory. In particular, I studied problems on temporal graphs following an algorithmic approach, trying to design efficient algorithms and proving lower bounds.

I will take a step back and start from graphs. Graphs are a mathematical model that represents the way entities of a certain set are linked together. For instance, these entities can be persons, computers or even places. Most of the time, when we consider such entities that exist in an actual system, their relations, and thus the way they are linked, change over time. Temporal graphs are an extension of graphs that capture this dynamic behavior. In this context, the links can be available at certain times and unavailable at others. I think temporal graphs are important as they can find application in a huge variety of domains, since many networks have inherent dynamic behavior.

As mentioned earlier, the applications of this research are numerous, but it is helpful to consider different models of temporal graphs to better fit the application at hand. In particular the length, or another property of a link, that could classically be captured by the weight of an arc, can now change as an arbitrary function of time.

For example, a temporal graph can model the interactions in a group of people, using a record of the time instants at which individuals have been in contact. People are represented by vertices, and interactions are represented by edges equipped with time labels. A different model can describe a road network. Each crossing is represented by a vertex, and each segment of the road connecting two crossings is an edge equipped with a function that describes the amount of time it takes to traverse that portion of the road at different times of the day.

This way it is possible to define models in the context of the already mentioned road networks, but also public transit networks, mobile and distributed networks, protein interaction networks, and several others.

I will soon begin working at a Joint Research Center of the European Commission. My task will consist in doing research and analysis in the field of transport networks. In particular, the position is part of the unit dealing with “Economics of climate change, energy and transport”. I will develop models and algorithms to produce quantitative analysis that support ex-ante impact assessments of transport policies in the EU agenda, also in relation to decarbonisation and externalities. I am particularly happy to have found an employment where I can put into practical use the expertise and theoretical knowledge I developed during my PhD studies. This way I will be able to tackle problems that are closer to reality and have the chance to have a positive impact on our surroundings.