BEGIN:VCALENDAR
VERSION:2.0
PRODID:researchseminars.org
CALSCALE:GREGORIAN
X-WR-CALNAME:researchseminars.org
BEGIN:VEVENT
SUMMARY:Ziad Ismaili  Alaoui (University of Liverpool)
DTSTART:20261120T130000Z
DTEND:20261120T140000Z
DTSTAMP:20261118T000758Z
UID:TheoryCSBham/89
DESCRIPTION:Title: <a href="https://researchseminars.org/talk/TheoryCSBham
 /89/">Space-Efficient Hierholzer</a>\nby Ziad Ismaili  Alaoui (University 
 of Liverpool) as part of University of Birmingham theoretical computer sci
 ence seminar\n\nInteractive livestream: https://bham-ac-uk.zoom.us/j/81873
 335084?pwd=T1NaUFg2U1l6d0RLL2RlTzFBam1IUT09\nLecture held in LG23\, Comput
 er Science.\n\nAbstract\nHere is a popular challenge: Can you copy a given
  drawing without lifting your pen or tracing any line more than once? A fa
 miliar example is the "Haus vom Nikolaus" (house of Santa Claus): a square
  with both diagonals and a triangular roof. In graph-theoretic terms\, thi
 s is the same as asking for an Eulerian trail\; that is\, a walk that trav
 erses every edge exactly once. (In this talk\, we focus on Eulerian cycles
 \, where the endpoints of the trail are equal.) The question of finding Eu
 lerian 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 grap
 h theory.\n\n\nHierholzer's algorithm is a classical method for computing 
 Eulerian cycles. Standard implementations run in optimal $O(m+n)$ time\, w
 here $n$ and $m$ are the numbers of vertices and edges\, but use $O(m)$ wo
 rds of working memory. (Here\, working memory is the auxiliary storage use
 d 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? \n\nIn this talk\, we presen
 t two variants of Hierholzer's algorithm that achieve exactly this\, one f
 or 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 significan
 t for dense graphs and for multigraphs with many parallel edges\, where $m
 $ can be much larger than $n$. Also\, both algorithms are simple to descri
 be and easy to implement\, and yet they rely on substantially different id
 eas that do not easily carry over between the directed and undirected case
 s. We explain these ideas and how they make it possible to output an entir
 e Eulerian cycle efficiently without ever storing it.\n\nJoint work with: 
 (directed case) Detlef Plump (University of York) and Sebastian Wild (Univ
 ersity of Marburg)\; (undirected case) Elena Grigorescu (University of Wat
 erloo)\, Tamio-Vesa Nakajima (University of Marburg)\, Shayan Shirazi Mofr
 ad (University of Waterloo) and Sebastian Wild (University of Marburg).\n
LOCATION:https://researchseminars.org/talk/TheoryCSBham/89/
URL:https://bham-ac-uk.zoom.us/j/81873335084?pwd=T1NaUFg2U1l6d0RLL2RlTzFBa
 m1IUT09
END:VEVENT
END:VCALENDAR
