Exact algorithms for the Steiner tree problem

general weighted graphs in time O*(3k), where k is the number of the terminals.
Firstly, we present two exact algorithms for the Steiner tree problem. The first one improves the running time of algorithm to O*(2.684k) by showing that the optimum Steiner tree T can be partitioned into T = T1 v T2 v T3 in a certain way such that
each Ti is a minimum Steiner tree in a suitable contracted graph Gi with less than k/2 terminals. The second algorithm is in time of O*((2 + delta)k) for any delta > 0.
Every rectilinear Steiner tree problem admits an optimal tree T* which is composed of tree stars. Moreover, the currently fastest algorithm for the rectilinear Steiner tree problem proceeds by composing an optimum tree T* from tree star components in
the cheapest way. F¨oßmeier and Kaufmann showed that any problem instance with k terminals has a number of tree stars in between 1.32k and 1.38k. We obtain a forbidden case for tree star, which is followed by a way to calculate the upper bound of the tree
stars. Meanwhile we determine the exact bound as O*(rho^k) where rho is approximately 1.357. Two new forbidden cases are obtained for the candidate component, and the new upper bound O*(1.337k) is achieved correspondingly. A new necessary condition, so called “two
layer condition” is presented as well for the tree star to be a candidate component.