Space-Efficient Hierholzer
Ziad Ismaili Alaoui (University of Liverpool)
| Fri Nov 20, 13:00-14:00 (3 days from now) | |
| Lecture held in LG23, Computer Science. |
Abstract: Here is a popular challenge: Can you copy a given drawing without lifting your pen or tracing any line more than once? A familiar example is the "Haus vom Nikolaus" (house of Santa Claus): a square with both diagonals and a triangular roof. In graph-theoretic terms, this is the same as asking for an Eulerian trail; that is, a walk that traverses every edge exactly once. (In this talk, we focus on Eulerian cycles, where the endpoints of the trail are equal.) The question of finding Eulerian cycles or characterising which graphs have one goes back to Euler's work on the bridges of Königsberg, which many cite as the birth of graph theory.
Hierholzer's algorithm is a classical method for computing Eulerian cycles. Standard implementations run in optimal $O(m+n)$ time, where $n$ and $m$ are the numbers of vertices and edges, but use $O(m)$ words of working memory. (Here, working memory is the auxiliary storage used during the computation. It excludes the input graph, which is read-only, and the output, which is written sequentially to an append-only stream.) A natural question is: Can we keep this running time while using memory proportional only to the number of vertices?
In this talk, we present two variants of Hierholzer's algorithm that achieve exactly this, one for directed and one for undirected multigraphs: both run in $O(m+n)$ time using only $O(n)$ words of working memory. The savings are most significant for dense graphs and for multigraphs with many parallel edges, where $m$ can be much larger than $n$. Also, both algorithms are simple to describe and easy to implement, and yet they rely on substantially different ideas that do not easily carry over between the directed and undirected cases. We explain these ideas and how they make it possible to output an entire Eulerian cycle efficiently without ever storing it.
Joint work with: (directed case) Detlef Plump (University of York) and Sebastian Wild (University of Marburg); (undirected case) Elena Grigorescu (University of Waterloo), Tamio-Vesa Nakajima (University of Marburg), Shayan Shirazi Mofrad (University of Waterloo) and Sebastian Wild (University of Marburg).
computer science theoryMathematics
Audience: researchers in the topic
University of Birmingham theoretical computer science seminar
Series comments: Meeting ID: 818 7333 5084 ~ Password: 217
| Organizers: | Namrata*, Pouya Partow*, Cristina Matache* |
| *contact for this listing |
