Tata Institute of Fundamental Research

Finding Euler Tours in One Pass in the W-Streaming Model with $\mathcal{O}(n\log n)$ Memory

STCS Seminar
Speaker: Anand Srivastav (University of Kiel Christian-Albrechts Platz 4 24118 Kiel Germany)
Organiser: Jaikumar Radhakrishnan
Date: Monday, 27 Nov 2017, 10:15 to 11:15
Venue: A-201 (STCS Seminar Room)

(Scan to add to calendar)
Abstract:  We study the problem of finding 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 the number of nodes resp.\ edges of $G$.  Our main result is the first one 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 previously 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 with $\omega(n)$ edges this is non-constant. (The talk is based on joint work with Christian Glazik, Jan Schiemann.)