A Polynomial-time algorithm for computation of the Tutte polynomials of graphs of bounded treewidth

Artur Andrzejak
Institut für Informatik
Freie Universität Berlin

Report B 95-16 December 1995

Get the report here or by anonymous ftp: 
Server: fubinf.inf.fu-berlin.de
File:   pub/reports/tr-b-95-16.ps.gz
For each fixed, positive integer k we give an algorithm which decides if a given graph G has treewidth at most k and if so, it computes the Tutte polynomial of G in time $0((2n)^{3+2 log_{2}(c_{1}/ log_{2}(\frac{5}{4})}$, where $c_{1}$ is twice the number of partitions of a set with 3k + 3 elements. The decision if G has treewidth at most k can be obtained in linear time due to an algorithm of H. Bodlaender.