Abstract
The Dreyfus–Wagner algorithm is a well-known dynamic programming method for computing minimum Steiner trees in general weighted graphs in time O *(3k), where k is the number of terminal nodes to be connected. We improve its running time to O *(2.684k) 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.386k). In this case, our splitting technique yields an improvement to O *(2.335k).
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
Downey RG, Fellows MR (1999). Parameterized complexity. Springer, Berlin
Dreyfus SE, Wagner RA (1972). The Steiner problem in graphs. Networks 1:195–207
Fößmeier U, Kaufmann M (2000). On exact solutions for the rectilinear Steiner tree problem Part 1: Theoretical results. Algorithmica 26:68–99
Ganley JL, Cohoon JP (1994) Optimal rectilinear Steiner minimal trees in O(n 2 2.62n) time. In: Proceedings of the 6th Canadian conference on computational geometry, pp 308–313
Garey M, Johnson D (1977). The rectilinear Steiner tree problem is NP-complete. SIAM J Appl Math 32(4):826–834
Gröpl C, Hougardy S, Nierhoff T, Prömel HJ (2001). Approximation algorithms for the Steiner tree problem in graphs. In: Cheng X, Du D-Z (eds) Steiner trees in industries. Kluwer, Dordrecht
Hwang FK (1976). On Steiner minimal trees with rectilinear distance. SIAM J Appl Math 30(1):104–114
Warme DM, Winter P, Zachariasen M (2000). Exact algorithms for plane Steiner tree problems: a computational study. In: Du DZ, Smith JM, Rubinstein JH (eds) Advances in Steiner trees. Kluwer, Dordrecht
Zachariasen M (2001). The Rectilinear Steiner tree problem: A tutorial. In: Cheng X, Du D-Z (eds) Steiner trees in industries. Kluwer, Dordrecht
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Fuchs, B., Kern, W. & Wang, X. Speeding up the Dreyfus–Wagner algorithm for minimum Steiner trees. Math Meth Oper Res 66, 117–125 (2007). https://doi.org/10.1007/s00186-007-0146-0
Received:
Revised:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s00186-007-0146-0