Algorithmic Problems on Temporal Graphs

A temporal graph is a graph whose edge set changes over a sequence of discrete time steps. This can be viewed as a discrete sequence G_1, G_2, ... of static graphs, each with a fixed vertex set V. Research in this area is motivated by the fact that many modern systems are highly dynamic and relations (edges) between objects (vertices) vary with time. Although static graphs have been extensively studied for decades from an algorithmic point of view, we are still far from having a concrete set of structural and algorithmic principles for temporal graphs. Many notions and algorithms from the static case can be naturally transferred in a meaningful way to their temporal counterpart, while in other cases new approaches are needed to define the appropriate temporal notions. In particular, some problems become radically different, and often substantially more difficult, when the time dimension is additionally taken into account. In this talk we will discuss some natural but only recently introduced temporal problems and some algorithmic approaches to them.

Biography

George B. Mertzios received his Diplom (with Distinction) in Mathematics and Informatics from the Technische Universitaet Muenchen, Germany (2005) and his Ph.D. in Computer Science from the RWTH Aachen University, Germany (2009). From 2010 to 2011 he worked as a Postdoctorate Researcher at the Technion - Israel Institute of Technology, and at the Caesarea Rothschild Institute for Computer Science, University of Haifa, Israel. In 2012 he served as an Invited Assistant Professor at the University of Bordeaux/CNRS, France. He joined Durham University in 2011 as a Lecturer in Computer Science, where he is now an Associate Professor. His research areas include efficient graph algorithms, computational complexity, and parameterized complexity. Since 2013 his research mainly focuses in temporal graphs and algorithms, which is an emerging and still growing field of computer science, and he had the privilege to help shaping this field with his early contributions. He is one of the founders, and a member of the Advisory Board, of the international conference SAND (Symposium on Algorithmic Foundations of Dynamic Networks) and he co-organizes every year since 2018 the annual satellite workshop of ICALP on temporal graphs.