Abstract
A special case of thebottleneck Steiner tree problem in the Euclidean plane was considered in this paper. The problem has applications in the design of wireless communication networks, multifacility location, VLSI routing and network routing. For the special case which requires that there should be no edge connecting any two Steiner points in the optimal solution, a 3-restricted Steiner tree can be found indicating the existence of the performance ratio √2. In this paper, the special case of the problem is proved to beNP-hard and cannot be approximated within ratio √2. First a simple polynomial time approximation algorithm with performance ratio √2 is presented. Then based on this algorithm and the existence of the 3-restricted Steiner tree, a polynomial time approximation algorithm with performance ratio—√2+∈ is proposed, for any ∈>0.
Similar content being viewed by others
Explore related subjects
Discover the latest articles, news and stories from top researchers in related subjects.References
Bern M, Plassmann P. The Steiner problem with edge lengths 1 and 2.Information Processing Letters, 1989, 32: 171–176.
Wang L, Du D Z. Approximations for a bottleneck Steiner tree problem.Algorithmica, 2002, 32: 554–561.
Wang L, Li Z. An approximation algorithm for a bottleneckk-Steiner tree problem in the Euclidean plane.Information Processing Letters, 2002, 81: 151–156.
Du D Z, Wang L, Xu B, The Euclidean bottleneck Steiner tree and Steiner tree with minimum number of Steiner points. InProceedings of the 7th Annual International Conference on Computing and Combinatorics, Guilin, China, August 2001,LNCS 2108, pp.509–518.
Gabow H N, Stallmann M. An augmenting path algorithm for linear matriod parity.Combinatorica, 1986, 6: 123–150.
Author information
Authors and Affiliations
Corresponding authors
Additional information
Supported partially by Shandong Province Excellent Middle-Aged and Young Scientists Encouragement Fund (Grant No.03BS004) and the Ministry of Education Study Abroad Returnees Research Start-up Fund, and the National Natural Science Foundation of China (Grant No.60273032).
Rights and permissions
About this article
Cite this article
Li, ZM., Zhu, DM. & Ma, SH. Approximation algorithm for bottleneck Steiner tree problem in the Euclidean plane. J. Comput. Sci. & Technol. 19, 791–794 (2004). https://doi.org/10.1007/BF02973441
Received:
Revised:
Published:
Issue Date:
DOI: https://doi.org/10.1007/BF02973441