Thore Husfeldt
News
New paper on the Tutte polynomial
I loved this the moment I saw it: the Tutte polynomial, an amazing structure in algebraic graph theory that can be used as a unifying framwork for lots and lots of science from other fields: models from statistical physics, graph colouring, knot theory, network theory. And now we have a paper on it!
We look at algorithms for computing the Tutte polynomial, and we even do what we claim to be interested in: compute the Tutte polynomial! So if you always wondered about the coefficient of x2y2 in Loupekine’s Second Snark: it’s 991226, found by our new, exact algorithm that runs in time roughly 2n.
The paper continues a very pleasant research collaboration with Andreas Björklund, Petteri Kaski, and Mikko Koivisto. Preprint at the ArXiv.
Update (April 2008): Now in polynomial space! And the paper covers the cover polynomial as well.
Tue, 15 Apr 2008 | Category: News | Permanent link