Evaluating a Weighted Graph Polynomial for Graphs of Bounded Tree-Width - Noble, S. D. (The Electronic Journal of Combinatorics, 2009)
We show that for any k there is a polynomial time algorithm to evaluate the weighted graph polynomial U of any graph with tree-width at most k at any point. For a graph with n vertices, the algorithm requires O(a_k n^2k+3) arithmetical operations, where a_k depends only on k.