research · Working draft
A smaller memory for Euler tours
The undirected case, a paper with wonderful collaborators, and an algorithm you can explore.
I helped resolve the undirected case of a space-efficient Euler-tour problem. The question sounds modest: can we walk every edge exactly once without keeping an edge-sized amount of extra memory?
Our answer is an O(m)-time algorithm using O(n) working memory for undirected multigraphs. The result belongs to a team: Elena Grigorescu, Ziad Ismaili Alaoui, Tamio-Vesa Nakajima, Sebastian Wild, and me.
What I enjoy most is the gap between the clean final statement and all the small decisions needed to make it true. I made an interactive visualization so those decisions are easier to see.