A polynomial time algorithm for computation of the Tutte polynomials of graphs of bounded treewidth
Artur Andrzejak · Refubium (Universitätsbibliothek der Freien Universität Berlin) · 1995
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 O((2 n) 3+2 log 2 (c 1 )= log 2 ( 5 4 ) ), where c1 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.