Space-Efficient Hierholzer: Eulerian Cycles in $\mathrm{O}(m)$ Time and $\mathrm{O}(n)$ Space
Fuente:
arXiv
Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866914117449678848 |
|---|---|
| author | Alaoui, Ziad Ismaili Plump, Detlef Wild, Sebastian |
| author_facet | Alaoui, Ziad Ismaili Plump, Detlef Wild, Sebastian |
| contents | 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 memory. This substantially improves the working space compared to standard implementations of Hierholzer's algorithm, which use $\mathrm{O}(m \lg n)$ bits of space. Our algorithm runs in linear time, like the classical versions, but avoids an $\mathrm{O}(m)$-size stack of vertices or storing information for each edge. To our knowledge, this is the first linear-time algorithm to achieve this space bound, and the method is very easy to implement. The correctness argument, by contrast, is surprisingly subtle; we give a detailed formal proof. The space savings are particularly relevant for dense graphs or multigraphs with large edge multiplicities. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2508_05251 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Space-Efficient Hierholzer: Eulerian Cycles in $\mathrm{O}(m)$ Time and $\mathrm{O}(n)$ Space Alaoui, Ziad Ismaili Plump, Detlef Wild, Sebastian Data Structures and Algorithms Discrete Mathematics 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 memory. This substantially improves the working space compared to standard implementations of Hierholzer's algorithm, which use $\mathrm{O}(m \lg n)$ bits of space. Our algorithm runs in linear time, like the classical versions, but avoids an $\mathrm{O}(m)$-size stack of vertices or storing information for each edge. To our knowledge, this is the first linear-time algorithm to achieve this space bound, and the method is very easy to implement. The correctness argument, by contrast, is surprisingly subtle; we give a detailed formal proof. The space savings are particularly relevant for dense graphs or multigraphs with large edge multiplicities. |
| title | Space-Efficient Hierholzer: Eulerian Cycles in $\mathrm{O}(m)$ Time and $\mathrm{O}(n)$ Space |
| topic | Data Structures and Algorithms Discrete Mathematics |
| url | https://arxiv.org/abs/2508.05251 |