Years and Authors of Summarized Original Work
2006; Du, Graham, Pardalos, Wan, Wu, Zhao
Definition
Given a set of points, called terminals, in a metric space, the problem is to find the shortest tree interconnecting all terminals. There are three important metric spaces for Steiner trees, the Euclidean plane, the rectilinear plane, and the edge-weighted network. The Steiner tree problems in those metric spaces are called the Euclidean Steiner tree (EST), the rectilinear Steiner tree (RST), and the network Steiner tree (NST), respectively. EST and RST have been found to have polynomial-time approximation schemes (PTAS) by using adaptive partition. However, for NST, there exists a positive number r such that computing r-approximation is NP-hard. So far, the best performance ratio of polynomial-time approximation for NST is achieved by k-restricted Steiner trees. However, in practice, the iterated 1-Steiner tree is used very often. Actually, the iterated 1-Steiner was proposed as a...
This is a preview of subscription content, log in via an institution to check access.
Recommended Reading
Arora S (1996) Polynomial-time approximation schemes for Euclidean TSP and other geometric problems. In: Proceedings of the 37th IEEE symposium on foundations of computer science, pp 2–12
Berman P, Ramaiyer V (1994) Improved approximations for the Steiner tree problem. J Algorithms 17:381–408
Bern M, Plassmann P (1989) The Steiner problem with edge lengths 1 and 2. Inf Proc Lett 32:171–176
Chang SK (1972) The generation of minimal trees with a Steiner topology. J ACM 19:699–711
Chang SK (1972) The design of network configurations with linear or piecewise linear cost functions. In: Symposium on computer-communications, networks, and teletraffic. IEEE Computer Society Press, Los Alamitos, pp 363–369
Crourant R, Robbins H (1941) What is mathematics? Oxford University Press, New York
Du DZ, Hwang FK (1990) The Steiner ratio conjecture of Gilbert-Pollak is true. Proc Natl Acad Sci USA 87:9464–9466
Du DZ, Zhang Y, Feng Q (1991) On better heuristic for Euclidean Steiner minimum trees. In: Proceedings of the 32nd FOCS. IEEE Computer Society Press, Los Alamitos
Du DZ, Graham RL, Pardalos PM, Wan PJ, Wu W, Zhao W (2008) Analysis of greedy approximations with nonsubmodular potential functions. In: Proceedings of 19th ACM-SIAM symposium on discrete algorithms (SODA). ACM, New York, pp 167–175
Kahng A, Robins G (1990) A new family of Steiner tree heuristics with good performance: the iterated 1-Steiner approach. In: Proceedings of IEEE international conference on computer-aided design, Santa Clara, pp 428–431
Wolsey LA (1982) An analysis of the greedy algorithm for the submodular set covering problem. Combinatorica 2:385–393
Robin G, Zelikovsky A (2000) Improved Steiner trees approximation in graphs. In: SIAM-ACM symposium on discrete algorithms (SODA), San Francisco, pp 770–779
Smith JM, Lee DT, Liebman JS (1981) An O(NlogN) heuristic for Steiner minimal tree problems in the Euclidean metric. Networks 11:23–39
Zelikovsky AZ (1993) The 11/6-approximation algorithm for the Steiner problem on networks. Algorithmica 9:463–470
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2014 Springer Science+Business Media New York
About this entry
Cite this entry
Wu, W., Huang, Y. (2014). Steiner Trees. In: Kao, MY. (eds) Encyclopedia of Algorithms. Springer, Boston, MA. https://doi.org/10.1007/978-3-642-27848-8_403-2
Download citation
DOI: https://doi.org/10.1007/978-3-642-27848-8_403-2
Received:
Accepted:
Published:
Publisher Name: Springer, Boston, MA
Online ISBN: 978-3-642-27848-8
eBook Packages: Springer Reference Computer SciencesReference Module Computer Science and Engineering