Speaker: Kitty Meeks (University of Glasgow)
Abstract: Temporal graphs - in which the edge-set changes over time - offer a valuable mathematical abstraction of many real-world systems, from transportation networks to social contact networks. A crucial feature of such systems that can be captured by temporal graphs is the temporal restriction on travel around the graph: if we arrive at vertex v at time t, we can only continue along an edge which appears in the graph at some time later than t. The requirement to use only these so-called temporal paths makes many computational problems much harder in temporal graphs than in the static setting. In this talk I will illustrate how certain graph exploration problems that are well-known to be polynomial-time solvable in the static setting become intractable on temporal graphs, even when strong structural restrictions are placed on the underlying static graph (where an edge is included if and only if it appears at least once during the lifetime of the graph). This motivates the development of new graph parameters that describe temporal structure: I will introduce two new parameters of this kind, and demonstrate how they can be used to obtain parameterised algorithms for specific problems related to exploration and reachability in temporal graphs.
Time and date: 02/12/2021 ar 14:30 (Paris time)