Temporal Graphs: Algorithms and complexity
Eleni Akrida
We discuss here the notion of temporal graphs, which are abstract models of networks that change as time progresses. In particular, a temporal graph on an underlying graph G is such that the edges of G have labels that are positive integers indicating discrete times (moments) of availability. A basic notion that arises from that definition is that of a journey, which extends the notion of a path in static graphs: it is a path in which subsequent edges appear with increasing labels.
In this talk, we will present recent work on temporal graphs hrough the lens of algorithms and complexity. We will examine foremost journeys, design issues of temporal networks, as well as issues of traversal including temporal variants of the Travelling salesman Problem.