 |
|
|||||||||||||||||||||||||||||||
|
||||||||||||||||||||||||||||||||
 |
||||||||||||||||||||||||||||||||
|
Prof. Thore Husfeldt: Computing the Tutte polynomial in vertex-exponential time(Joint work with Andreas Björklund, Petteri Kaski, Mikko Koivisto) The deletion--contraction algorithm is perhaps the most popular method for computing a host of fundamental graph invariants such as the chromatic, flow, and reliability polynomials in graph theory, the Jones polynomial of an alternating link in knot theory, and the partition functions of the models of Ising, Potts, and Fortuin--Kasteleyn in statistical physics. Prior to this work, deletion--contraction was also the fastest known general-purpose algorithm for these invariants, running in time roughly proportional to the number of spanning trees in the input graph. After a leisurely introduction to the Tutte polynomial and its variants I will present a substantially faster algorithm that computes the Tutte polynomial--and hence, all the aforementioned invariants and more--of an arbitrary graph in time exponential in the number of vertices. Falls dieser Text Formeln enthält, die nicht dargestellt werden können, finden Sie hier die dvi- bzw. die pdf-Version. |
HV