## Speaker:

## Affiliation:

University of Kiel Christian-Albrechts Platz 4 24118 Kiel Germany

## Time:

## Venue:

- A-201 (STCS Seminar Room)

## Organisers:

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