Improved Steiner tree algorithms for bounded treewidth

We propose a new algorithm that solves the Steiner tree problem on graphs with vertex set V   to optimality in O(Btw+22⋅tw⋅|V|) time, where tw is the graphʼs treewidth and the Bell number  BkBk is the number of partitions of a k  -element set. This is a linear-time algorithm for graphs with fixed treewidth and a polynomial algorithm for tw∈O(log|V|/loglog|V|).While being faster than the previously known algorithms, the coloring scheme used in our algorithm can be extended to give new, improved algorithms for the prize-collecting Steiner tree as well as the k-cardinality tree problems with similar runtime bounds.