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 * (3 k ), where k is the number of terminal nodes to be connected. We improve its running time to O * (2.684 k ) by showing that the optimum Steiner tree T can be partitioned into T = T 1 ∪ T 2 ∪ T 3 in a certain way such that each T i is a minimum Steiner tree in a suitable contracted graph G i with less than $${\frac{k}{2}}$$ terminals. In the rectilinear case, there exists a variant of the dynamic programming method that runs in O * (2.386 k ). In this case, our splitting technique yields an improvement to O * (2.335 k ). Copyright Springer-Verlag 2007