BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//University of Liverpool Computer Science Seminar System//v2//EN
BEGIN:VEVENT
DTSTAMP:20260922T122039Z
UID:Seminar-dept-1278@lxserverM.csc.liv.ac.uk
ORGANIZER:CN=Lutz Oettershagen:MAILTO:Lutz.Oettershagen@liverpool.ac.uk
DTSTART:20250701T130000
DTEND:20250701T140000
SUMMARY:School Seminar Series
DESCRIPTION:Nicolas Klodt: Exploration of Random Temporal Graphs\n\nThe temporal exploration problem (TEXP) asks for a walk in a given temporal graph, where at most one edge is traversed in each time step, and all vertices are visited. In this talk we will consider the temporal exploration problem (TEXP) on a model of random temporal graphs which are connected in each time step. It is known that there are n-vertex temporal graphs which are connected in each time step but require $\Omega(n^2)$ steps to explore, our aim is to understand what happens against a random adversary.\n\n\n\nIn our model an adversary supplies a measure $\mu$ supported on a set of (labelled) spanning trees on $n$ vertices, and we obtain a (random) temporal graph by sampling a spanning tree from $\mu$ at each time step independently. We show that, for any $\mu$, w.h.p. there is a schedule which explores the corresponding temporal graph in time $O(n^{3/2})$. Furthermore, we provide an example of $\mu$ which requires $\Omega(n^{3/2})$ steps to explore in expectation.\n\n\n\nThis is joint work with Samuel Baguley, Andreas Göbel, George Skretas, John Sylvester and Viktor Zamaraev\n\nhttps://www.csc.liv.ac.uk/research/seminars/abstract.php?id=1278
LOCATION:Ashton Lecture Theatre
END:VEVENT
END:VCALENDAR