BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//labri.fr//NONSGML kigkonsult.se iCalcreator 2.41.92//
CALSCALE:GREGORIAN
METHOD:PUBLISH
UID:29f1c120-b8bc-48b1-8768-69025a2ebe32
X-WR-CALNAME:GT AlgoDist\, «In Search of the Lost Tree: Hardness and relaxa
 tion of spanning trees in temporal graphs»\, Timothée Corsini
X-WR-TIMEZONE:Europe/Paris
BEGIN:VTIMEZONE
TZID:Europe/Paris
TZUNTIL:20251026T010000Z
BEGIN:STANDARD
TZNAME:CET
DTSTART:20231029T030000
TZOFFSETFROM:+0200
TZOFFSETTO:+0100
RDATE:20241027T030000
END:STANDARD
BEGIN:DAYLIGHT
TZNAME:CEST
DTSTART:20240331T020000
TZOFFSETFROM:+0100
TZOFFSETTO:+0200
RDATE:20250330T020000
END:DAYLIGHT
END:VTIMEZONE
BEGIN:VEVENT
UID:29f1c120-b8bc-48b1-8768-69025a2ebe32
DTSTAMP:20260409T160317Z
CLASS:PUBLIC
DESCRIPTION:Timothée Corsini\n\nTitle: In Search of the Lost Tree: Hardness
  and relaxation of spanning trees in temporal graphs\n\nAbstract:\n\nA gra
 ph whose edges only appear at certain points in time is called a temporal 
 graph (among other names). These graphs are temporally connected if all or
 dered pairs of vertices are connected by a path that traverses edges in ch
 ronological order (a temporal path). Reachability in temporal graphs depar
 ts significantly from standard reachability\; in particular\, it is not tr
 ansitive\, with structural and algorithmic consequences. For instance\, te
 mporally connected graphs do not always admit spanning trees\, i.e.\, subs
 ets of edges that form a tree and preserve temporal connectivity among the
  nodes. \n\nIn this talk\, we revisit fundamental questions about the loss
  of universality of spanning trees. We show that deciding if a spanning tr
 ee exists in a given temporal graph is NP-complete. What could be appropri
 ate replacement for the concept? Beyond having minimum size\, spanning tre
 es enjoy the feature of enabling reachability along the same underlying pa
 ths in both directions\, a pretty uncommon feature in temporal graphs. We 
 explore relaxations in this direction and show that testing the existence 
 of bidirectional spanning structures (bi-spanners) is tractable in general
 . On the down side\, finding minimum such structures is NP-hard even in si
 mple temporal graphs. Still\, the fact that bidirectionality can be tested
  efficiently may find applications\, e.g. for routing and security\, and t
 he corresponding primitive that we introduce in the algorithm may be of in
 dependent interest.\n\n\nhttps://algodist.labri.fr/index.php/Main/GT
DTSTART;TZID=Europe/Paris:20240410T110000
DTEND;TZID=Europe/Paris:20240410T120000
LOCATION:LaBRI salle 178 - lien visio https://webconf.u-bordeaux.fr/b/arn-4
 tr-7gp
SEQUENCE:0
SUMMARY:GT AlgoDist\, «In Search of the Lost Tree: Hardness and relaxation 
 of spanning trees in temporal graphs»\, Timothée Corsini
TRANSP:OPAQUE
END:VEVENT
END:VCALENDAR
