BEGIN:VCALENDAR
PRODID:-//eluceo/ical//2.0/EN
VERSION:2.0
CALSCALE:GREGORIAN
BEGIN:VEVENT
UID:www.tcs.tifr.res.in/event/1001
DTSTAMP:20230914T125946Z
SUMMARY:Fault-Tolerant Reachability and Strong-connectivity Structures
DESCRIPTION:Speaker: Keerti Choudhary (Weizmann Institute of Science\, Isra
 el)\n\nAbstract: \nAbstract: Reachability and strong-connectivity are som
 e of the fundamental graph problems. In the static setting\, both problems
  can be solved in O(m+n) time for any directed graph G with n vertices and
  m edges. However\, most real-world networks are prone to failures. The fa
 ilures are transient and occur for a small duration of time. Under such a 
 setting\, we would like to preprocess the graph to compute data-structures
  that can achieve robustness by being functional even after the occurrence
  of failures. In recent years\, researchers have studied various questions
  pertaining to connectivity\, distances\, routing\, min-cuts\, etc. in the
  domain of fault tolerance networks.\nIn this talk\, I will discuss the fo
 llowing questions:\n\n1. Can we compute a reachability tree in just linear
  time\, after the occurrence of a small number of failures?\n2. How fast c
 an we compute the strongly connected components\, again on the occurrence 
 of failures?\n3. Does there exist a sparse certificate for these structure
 s that remains valid even after a bounded number of failures?\nThe solutio
 ns to these problems employ extremely basic tools like max-flows\, min-cut
 s\, and heavy-path-decomposition.\n
URL:https://www.tcs.tifr.res.in/web/events/1001
DTSTART;TZID=Asia/Kolkata:20191003T113000
DTEND;TZID=Asia/Kolkata:20191003T123000
LOCATION:A-201 (STCS Seminar Room)
END:VEVENT
END:VCALENDAR