Department Seminar Series

Temporal Graph Realization Problems

25th March 2025, 13:00 add to calenderELEC204, 2th Floor Lecture Theater EEE
Thomas Erlebach
Durham University

Abstract

Temporal graphs are graphs that have a fixed vertex set but whose edge set can change in every time step. They can model time-varying or dynamic networks arising in many application areas such as public transport networks, social networks, and mobile or reconfigurable communication networks. A temporal graph can be represented as a graph G=(V,E) together with a labelling function that maps each edge to the set of time steps during which it is present. An edge e present at time t is referred to as a time edge. A temporal path from u to v is then a sequence of time edges that form a path from u to v and have increasing time labels. Temporal graph realization refers to problems of the following kind: Given some requirements about the temporal paths that we would like to have between the vertices of the graph, does there exist a temporal graph that meets these requirements? In this talk, we will discuss results for such temporal graph realization problems where the requirements specify the fastest travel durations (arrival time minus departure time of a temporal path) for all pairs of vertices or specify for each pair (u,v) of vertices whether there should be a temporal path from u to v or not.

The talk is based on a SAND 2024 paper with Nils Morawietz and Petra Wolf, and on unpublished work with Othon Michail and Nils Morawietz.
add to calender (including abstract)

Biography

Thomas Erlebach received a PhD in Computer Science from Technische Universität München in 1999. He was an Assistant Professor in Theory of Communication Networks at ETH Zürich from 2000 to 2004 and then Reader and Professor (from 2007) at University of Leicester until 2021. Since September 2021, he has been a Professor in the Department of Computer Science at Durham University. His research interests lie in approximation and online algorithms for combinatorial optimisation problems, algorithmic aspects of communication networks, temporal graphs, and computing with explorable uncertainty.

Additional Materials