Speeding up the Dreyfus-Wagner algorithm for minimum Steiner trees


Fuchs, Bernard and Kern, Walter and Wang, Xinhui (2007) Speeding up the Dreyfus-Wagner algorithm for minimum Steiner trees. Mathematical methods of operations research, 66 (1). pp. 117-125. ISSN 1432-2994

[img] PDF
Restricted to UT campus only
: Request a copy
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)$.
Item Type:Article
Copyright:© 2007 Springer
Electrical Engineering, Mathematics and Computer Science (EEMCS)
Research Group:
Link to this item:http://purl.utwente.nl/publications/61920
Official URL:https://doi.org/10.1007/s00186-007-0146-0
Export this item as:BibTeX
HTML Citation
Reference Manager


Repository Staff Only: item control page

Metis ID: 241914