{"ID":2885158,"CreatedAt":"2026-06-01T04:54:23.091178241Z","UpdatedAt":"2026-06-01T04:54:23.091178241Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2508.05251","arxiv_id":"2508.05251","title":"Space-Efficient Hierholzer: Eulerian Cycles in $\\mathrm{O}(m)$ Time and $\\mathrm{O}(n)$ Space","abstract":"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.","short_abstract":"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...","url_abs":"https://arxiv.org/abs/2508.05251","url_pdf":"https://arxiv.org/pdf/2508.05251v2","authors":"[\"Ziad Ismaili Alaoui\",\"Detlef Plump\",\"Sebastian Wild\"]","published":"2025-08-07T10:40:45Z","proceeding":"cs.DS","tasks":"[\"cs.DS\",\"cs.DM\"]","methods":"[]","has_code":false}