Speeding up the Dreyfus–Wagner algorithm for minimum Steiner trees

The Dreyfus–Wagner algorithm is a well-known dynamic programming method for computing minimum Steiner trees in general weighted graphs in time O*(3k), where k is the number of terminal nodes to be connected. We improve its running time to O*(2.684k) by showing that the optimum Steiner tree T can be partitioned into T = T1∪ T2 ∪ T3 in a certain way such that each Ti is a minimum Steiner tree in a suitable contracted graph Gi with less than \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${\frac{k}{2}}$$\end{document} terminals. In the rectilinear case, there exists a variant of the dynamic programming method that runs in O*(2.386k). In this case, our splitting technique yields an improvement to O*(2.335k).