Space-Efficient Hierholzer: Eulerian Cycles in $\mathrm{O}(m)$ Time and $\mathrm{O}(n)$ Space

Ziad Ismaili Alaoui, Detlef Plump, Sebastian Wild

We describe a simple variant of Hierholzer's algorithm that finds an Eulerian cycle in a (multi)graph with $n$ vertices and $m$ edges using $\mathrm{O}(n\lg m)$ bits of working me…