[an error occurred while processing this directive]
An error occured whilst processing this directive
Approximating the Tutte polynomial: a status report
University of Edinburgh
4pm Tuesday 25th April 2006
Room 2511, JCMB, King's Buildings
Abstract
The (classical) Tutte polynomial of a graph G is a two-variable
polynomial T(G;x,y) that encodes much information about G. The number
of spanning trees in G, the number of acyclic orientations of G and
the partition function of the q-state Potts model are all
specialisations of the Tutte polynomial. From a complexity-theoretic
point of view, "mapping the Tutte plane" amounts to determining the
computational complexity of evaluating T(G;x,y), given G, for each
rational pair (x,y). For exact computation, the mapping was done in
detail by Jaeger, Vertigan and Welsh. For approximate computation
(within specified relative error) much less was known. Some progress
has recently been made, but there is still a good deal of terra
incognita. The later stages of the talk will touch on joint work with
Leslie Goldberg (Warwick).
An error occured whilst processing this directive