Seminar series
Date
Tue, 12 Oct 2010
Time
14:30 -
15:30
Location
L3
Speaker
Mary Cryan
Organisation
Edinburgh
The problem of checking existence for an Euler tour of a graph is trivial (are all vertex degrees even?). The problem of counting (or even approximate counting) Euler tours seems to be very difficult. I will describe two simple classes of graphs where the problem can be
solved exactly in polynomial time. And also talk about the many many classes of graphs where no positive results are known.