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.gzFor 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.