Speaker
Dr
Petteri Kaski
(HIIT)
Description
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.
<rb>
Here, we give a substantially faster algorithm that computes
the Tutte polynomial---and hence, all the aforementioned
invariants and more---of an arbitrary graph in time and
space 2^nn^{O(1)}.
Joint work with Andreas Björklund, Thore Husfeldt, and Mikko Koivisto.
Joint work with Andreas Björklund, Thore Husfeldt, and Mikko Koivisto.
