BEGIN:VCALENDAR
PRODID:-//eluceo/ical//2.0/EN
VERSION:2.0
CALSCALE:GREGORIAN
BEGIN:VEVENT
UID:www.tcs.tifr.res.in/event/827
DTSTAMP:20230914T125939Z
SUMMARY:Finding Euler Tours in One Pass in the W-Streaming Model with $\\ma
 thcal{O}(n\\log n)$ Memory
DESCRIPTION:Speaker: Anand Srivastav (University of Kiel Christian-Albrecht
 s Platz 4 24118 Kiel Germany)\n\nAbstract: \nWe study the problem of findi
 ng an Euler tour in an undirected graph $G$ in the W-Streaming model with 
 $\\mathcal{O}(n\\\,\\textrm{polylog}(n))$ RAM\, where $n$ resp.\\ $m$ is t
 he number of nodes resp.\\ edges of $G$.  Our main result is the first on
 e pass W-Streaming algorithm computing an Euler tour of $G$ in the form of
  an edge successor function with only $\\mathcal O(n \\log(n))$ RAM which 
 is optimal for this setting (e.g.\, Sun and Woodruff (2015)). The previous
 ly best-known result in this model is implicitly given by Demetrescu et al
 .\\ (2010) with the parallel algorithm of Atallah and Vishkin (1984) using
  $\\mathcal O(m/n)$ passes under the same RAM limitation.  For graphs wit
 h $\\omega(n)$ edges this is non-constant. (The talk is based on joint wor
 k with Christian Glazik\, Jan Schiemann.)\n
URL:https://www.tcs.tifr.res.in/web/events/827
DTSTART;TZID=Asia/Kolkata:20171127T101500
DTEND;TZID=Asia/Kolkata:20171127T111500
LOCATION:A-201 (STCS Seminar Room)
END:VEVENT
END:VCALENDAR