Biography

Arnaud Casteigts is interested in the many facets of theoretical computer science and network science, ranging from distributed algorithms to graph theory, computational complexity, and quantum algorithms. A good share of his work is devoted to the modeling of dynamic networks (e.g. networks of robots/drones, wireless sensors, social interaction) using temporal graph theory, with a focus on the computational complexity of connectivity questions in these graphs. He joined the University of Geneva as a professor in 2023, where he is heading the ALGO group in the Computer Science department. He earned a PhD from the University of Bordeaux in 2007, spent five years as a postdoc at the University of Ottawa, then returned to Bordeaux in 2012 as an assistant (then associate and full) professor in the Combinatorics and Algorithm department. He is eager to discover the landscape of operations research and graph theory in Switzerland.

Presentation

Title

Temporal graph theory: paradigm and algorithmic challenges

Abstract

A temporal graph is a graph whose edges are only present at certain points in time. These graphs received a growing attention over the past two decades, due to their ability to model various types of dynamic networks. On the theoretical side, temporal graphs are quite different from static graphs. For instance, reachability (defined in terms of paths that traverses edges in chronological order) is not transitive. This and other features have important consequences, both structural and algorithmic, most questions becoming computationally hard. In this talk, I will review some basic results in this young field, with a focus on reachability questions.