Evaluating a weighted graph polynomial for graphs of bounded tree-width (Q1028845)

Summary: 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\).