BEGIN:VCALENDAR
CALSCALE:GREGORIAN
PRODID:iCalendar-Ruby
VERSION:2.0
BEGIN:VEVENT
DESCRIPTION: A graph whose edges only appear at certain points in time is c
 alled a temporal graph. Such a graph is temporally connected if each ordere
 d pair of vertices is connected by a path which traverses edges in chronolo
 gical order (i.e.\, a temporal path). In this talk\, I will focus on the co
 ncept of a temporal spanner\, which is a subgraph of the input temporal gra
 ph that preserves temporal connectivity using as few edges (or labels) as p
 ossible. In stark contrast with standard graphs\, it turns out that linear 
 size spanners\, and in fact\, even sparse spanners (i.e.\, spanners with o(
 n ^2 ) edges) do not always exist in temporal graphs. After presenting basi
 c notions and reviewing these astonishing negative results\, I will present
  some good news as well\; namely\, sparse spanners always exist in  *some* 
  natural classes of temporal graphs. These include the cases when the under
 lying graph is complete (this talk) or when the labels are chosen at random
  (subsequent talk). If time permit\, I will present two open questions\, an
 d discuss some recent attempts at solving them. 
DTSTAMP:20211118T220000
DTSTART:20211206T141500
CLASS:PUBLIC
LOCATION:Online via Zoom \n 
SEQUENCE:0
SUMMARY:Arnaud Casteigts (Université de Bordeaux): Spanners and connectivit
 y problems in temporal graphs
UID:107919881@/www.mi.fu-berlin.de
URL:https://www.mi.fu-berlin.de/en/facetsofcomplexity/monday/20211206-L-Cas
 teigts.html
END:VEVENT
END:VCALENDAR