BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//Date iCal//NONSGML kigkonsult.se iCalcreator 2.20.2//
METHOD:PUBLISH
X-WR-CALNAME;VALUE=TEXT:Eventi DIAG
BEGIN:VTIMEZONE
TZID:Europe/Paris
BEGIN:STANDARD
DTSTART:20171029T030000
TZOFFSETFROM:+0200
TZOFFSETTO:+0100
TZNAME:CET
END:STANDARD
BEGIN:DAYLIGHT
DTSTART:20180325T020000
TZOFFSETFROM:+0100
TZOFFSETTO:+0200
TZNAME:CEST
END:DAYLIGHT
END:VTIMEZONE
BEGIN:VEVENT
UID:calendar.12934.field_data.0@www.u-gov-ricerca.uniroma1.it
DTSTAMP:20260409T073758Z
CREATED:20171025T101202Z
DESCRIPTION:We present randomized algorithms with a total update time of O~
 (m \sqrt{n}) for the problems of decremental single-source reachability an
 d decremental strongly connected components on directed graphs. This impro
 ves recent breakthrough results of Henzinger\, Krinninger and Nanongkai [S
 TOC 14\, ICALP 15]. In addition\, our algorithms are arguably simpler. In 
 this talk\, we are going to briefly review the Las Vegas algorithm by Rodi
 tty and Zwick [SICOMP 08] and the algorithm by Łącki [TALG 13]\, both with
  a total update time O(mn) (expected time in the case of the algorithm by 
 Roditty and Zwick). Our algorithms carefully combine these two results\, a
 long with new structural properties\, including a separation lemma in the 
 case of graphs with a large diameter.(Appeared in FOCS 2016. Joint work wi
 th Shiri Chechik\, Thomas Dueholm Hansen\, Giuseppe F. Italiano\, and Jaku
 b Łącki.)
DTSTART;TZID=Europe/Paris:20171108T120000
DTEND;TZID=Europe/Paris:20171108T120000
LAST-MODIFIED:20191008T082902Z
LOCATION:Room A4@DIAG\, via Ariosto 25\, ground floor
SUMMARY:Nikos Parotsidis: Decremental Single-Source Reachability and Strong
 ly Connected Components  - Nikos Parotsidis\, University of Rome Tor Verga
 ta
URL;TYPE=URI:http://www.u-gov-ricerca.uniroma1.it/node/12934
END:VEVENT
END:VCALENDAR