Personal tools
You are here: Home Events Lab lunch speakers 2010 Mary Cryan

Mary Cryan

A few easy cases for counting Euler tours

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 some verrrry simple classes of graphs where the problem can be solved exactly in polynomial time. And also describe the many many classes of graphs where no positive results are known.

(joint with P.Chebolu and R.Martin, and with P.Creed)

Document Actions