A couple of easy cases for counting Euler tours
|
Tue, 12/10/2010 14:30 |
Mary Cryan (Edinburgh) |
Combinatorial Theory Seminar  |
L3 |
| 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. | |||