Algorithms and Complexity on Temporal Graphs
A temporal graph is a graph that changes over time. Assuming discrete time and a fixed set $V$ of vertices, a temporal graph can be viewed as a discrete sequence $G_1, G_2, \ldots$ of static graphs, each with 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 substantially more difficult when the time dimension is additionally taken into account. In this talk we will introduce temporal graphs and we will survey recent algorithmic results.