### 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

## Cite this

Fuchs, B., Kern, W., & Wang, X. (2007). Speeding up the Dreyfus-Wagner algorithm for minimum Steiner trees.

*Mathematical methods of operations research*,*66*(LNCS4549/1), 117-125. https://doi.org/10.1007/s00186-007-0146-0