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 |
---|---|
Pages (from-to) | 117-125 |
Number of pages | 9 |
Journal | Mathematical methods of operations research |
Volume | 66 |
Issue number | LNCS4549/1 |
DOIs | |
Publication status | Published - Aug 2007 |
Keywords
- METIS-241914
- IR-61920
- EWI-11081