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.)
| 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.)