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(B-tw+2(2) . tw . vertical bar V vertical bar) time, where tw is the graph's treewidth and the Bell number B-k is the number of partitions of a k-element set. This is a lineartime algorithm for graphs with fixed treewidth and a polynomial algorithm for tw is an element of O( log vertical bar V vertical bar/log log vertical bar V vertical bar). 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. (C) 2012 Elsevier B.V. All rights reserved.