BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//University of Liverpool Computer Science Seminar System//v2//EN
BEGIN:VEVENT
DTSTAMP:20260914T003321Z
UID:Seminar-dept-1019@lxserverM.csc.liv.ac.uk
ORGANIZER:CN=Lutz Oettershagen:MAILTO:Lutz.Oettershagen@liverpool.ac.uk
DTSTART:20221110T100000
DTEND:20221110T110000
SUMMARY:School Seminar Series
DESCRIPTION:Prof. Arnaud Casteigts: Spanners and connectivity problems in temporal graphs\n\nA graph whose edges only appear at certain points in time is called a\n\ntemporal graph. These graphs are temporally connected if all the nodes\n\ncan reach each other through path that traverses edges in chronological\n\norder (i.e., a temporal path). In this talk, I will present some general\n\nfacts about temporal reachability. Then, I will focus on the particular\n\nproblem of finding small subgraphs that preserve temporal connectivity\n\n(i.e., a temporal spanner). Quite surprisingly, Axiotis and Fotakis\n\nshowed in [1] that small spanners do not always exist in temporal\n\ngraphs, in stark contrast with standard graphs. I will then review some\n\npositive results that we obtained recently, including the fact that\n\nspanners of size O(n log n) always exist in temporal cliques [2], and\n\nthat quasi-optimal spanners exist with high probability in random\n\ntemporal graphs [3].\n\n\n\n[1] Axiotis and Fotakis, On the size and the approximability of minimum\n\ntemporally connected subgraphs (ICALP 2016)\n\n[2] Casteigts, Peters, Schoeters, Temporal cliques admit sparse spanners\n\n(ICALP 2019)\n\n[3] Casteigts, Raskin, Renken, Zamaraev, Sharp thresholds in random\n\nsimple temporal graphs (FOCS 2021)\n\nhttps://www.csc.liv.ac.uk/research/seminars/abstract.php?id=1019
LOCATION:Zoom
END:VEVENT
END:VCALENDAR