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