##
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((2*n*)^{3+2 log_{2}(c_{1}/ log_{2}(\frac{5}{4})}$, where $c_{1}$ is twice the number of partitions of a set with 3*k* + 3 elements. The decision if * G* has treewidth at most *k* can be obtained in linear time due to an algorithm of H. Bodlaender.