BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//University of Liverpool Computer Science Seminar System//v2//EN
BEGIN:VEVENT
DTSTAMP:20260408T090815Z
UID:Seminar-dept-1311@lxserverA.csc.liv.ac.uk.csc.liv.ac.uk
ORGANIZER:CN=Lutz Oettershagen:MAILTO:Lutz.Oettershagen@liverpool.ac.uk
DTSTART:20260210T130000
DTEND:20260210T140000
SUMMARY:School Seminar Series
DESCRIPTION:Paul Bastide: Exploring temporal graphs\n\nA temporal graph G is a sequence of graphs G1, G2, ... , Gt on the same vertex set. In this talk, we are interested in the analogue of the Travelling Salesman Problem for temporal graphs. It is referred to in the literature as the Temporal Exploration Problem, and asks for the minimum length of an exploration of the graph, that is, a sequence of vertices such that at each time step t, one either stays at the same vertex or moves along a single edge of Gt.\n\n\n\nOne natural and still open case is when each graph Gt is connected and has bounded maximum degree. We present a short proof that any such graph admits an exploration in O(n^(3/2) log n^(1/2)) time steps. In fact, we deduce this result from a more general statement by introducing the notion of average temporal maximum degree. This more general statement improves the previous best bounds, under a unified approach, for several studied exploration problems.\n\n\n\nThis is based on joint work with Carla Groenland, Lukas Michel and Clément Rambaud.\n\nhttps://www.csc.liv.ac.uk/research/seminars/abstract.php?id=1311
LOCATION:Ashton Lecture Theatre
END:VEVENT
END:VCALENDAR