# Speeding up the Dreyfus-Wagner algorithm for minimum Steiner trees

Bernard Fuchs, Walter Kern, Xinhui Wang

6 Citations (Scopus)

### Abstract

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 \cup T_2 \cup 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 ${k\over 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)$.
Original language Undefined 117-125 9 Mathematical methods of operations research 66 LNCS4549/1 https://doi.org/10.1007/s00186-007-0146-0 Published - Aug 2007

• METIS-241914
• IR-61920
• EWI-11081