On the euclidean bottleneck full Steiner tree problem

ABSTRACT

Given two sets in the plane, R of n (terminal) points and S of m (Steiner) points, a full Steiner tree is a Steiner tree in which all points of R are leaves. In the bottleneck full Steiner tree (BFST) problem, one has to find a full Steiner tree T (with any number of Steiner points from S), such that the length of the longest edge in T is minimized, and, in the k-BFST problem, has to find a full Steiner tree T with at most k ≤ m Steiner points from S such that the length of the longest edge in T is minimized. The problems are motivated by wireless network design. In this paper, we present an exact algorithm of O((n+m)log²m) time to solve the BFST problem. Moreover, we show that the k-BFST problem is NP-hard and that there exists a polynomial-time approximation algorithm for the problem with performance ratio 4.

References

1. S. Arora. Polynomial time approximation schemes for Euclidean TSP and other geometric problems. Journal of the ACM, 45:735--782, 1998.
2. S. Arora, C. Lund, R. Motwani, M. Sudan, and M. Szegedy. Proof verification and hardness of approximation problems. In Proceedings of the 33rd Annual Symposium on Foundations of Computer Science (FOCS '92), pages 14--23, 1992.
3. S.W. Bae, C. Lee, and S. Choi. On exact solutions to the euclidean bottleneck Steiner tree problem. Information Processing Letters, 110:672--678, 2010.
4. P. Berman and V. Ramaiyer. Improved approximation for the Steiner tree problem. Journal of Algorithms, 17:381--408, 1994.
5. A. Borchers and D.Z. Du. The k-Steiner ratio in graphs. SIAM Journal on Computing, 26:857--869, 1997.
6. Y.H. Chen, C.L. Lu, and C.Y. Tang. On the full and bottleneck full Steiner tree problems. In Proceedings of the 9th Annual International Conference on Computing and Combinatorics (COCOON '03), volume 2697 of LNCS, pages 122--129, 2003.
7. X. Cheng and D.Z. Du. Steiner Tree in Industry. Kluwer Academic Publishers, Dordrecht, Netherlands, 2001.
8. T.H. Cormen, C.E. Leiserson, R.L. Rivest, and C. Stein. Introduction to Algorithms, 3rd edition. MIT Press, 2009.
9. M. de Berg, O. Cheong, M. Kreveld, and M. Overmars. Computational Geometry: Algorithms and Applications. Springer-Verlag, 2008.
10. D.E. Drake and S. Hougardy. On approximation algorithms for the terminal Steiner tree problem. Information Processing Letters, 89:15--19, 2004.
11. D.Z. Du, J.M. Smith, and J.H. Rubinstein. Advances in Steiner Tree. Kluwer Academic Publishers, Dordrecht, Netherlands, 2000.
12. C.W. Duin and A. Volgenant. The partial sum criterion for Steiner trees in graphs and shortest paths. European Journal of Operations Research, 97:172--182, 1997.
13. M.R. Garey, R.L. Graham, and D.S. Johnson. The complexity of computing Steiner minimal trees. SIAM Journal of Applied Mathematics, 32(4):835--859, 1977.
14. M.R. Garey and D.S. Johnson. The rectilinear Steiner tree problem is NP-complete. SIAM Journal of Applied Mathematics, 32(4):826--834, 1977.
15. S. Hougardy and H.J. Prommel. A 1.598 approximation algorithm for the Steiner problem in graphs. In Proceedings of the 10th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA '99), pages 448--453, 1999.
16. F.K. Hwang, D.S. Richards, and P. Winter. The Steiner Tree Problem. Annuals of Discrete Mathematics, Amsterdam, 1992.
17. A.B. Kahng and G. Robins. On Optimal Interconnection for VLSI. Kluwer Academic Publishers, Dordrecht, Netherlands, 1995.
18. Z.-M. Li, D.-M. Zhu, and S.-H. Ma. Approximation algorithm for bottleneck Steiner tree problem in the Euclidean plane. Journal of Computer Science and Technology, 19(6):791--794, 2004.
19. G.H. Lin and G.L. Xue. On the terminal Steiner tree problem. Information Processing Letters, 84:103--107, 2002.
20. C.L. Lu, C.Y. Tang, and R.C.T. Lee. The full Steiner tree problem. Theoretical Computer Science, 306(1--3):55--67, 2003.
21. F.V. Martinez, J.C. de Pina, and J. Soares. Algorithms for terminal Steiner trees. Theoretical Computer Science, 389(1--2):133--142, 2007.
22. G. Robbins and A. Zelikovsky. Improved Steiner tree approximation in graphs. In Proceedings of the 11th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA '00), pages 770--779, 2000.
23. M. Sarrafzadeh and C.K. Wong. Bottleneck Steiner trees in the plane. IEEE Transactions on Computers, 41(3):370--374, 1992.
24. L. Wang and D.-Z. Du. Approximations for a bottleneck Steiner tree problem. Algorithmica, 32:554--561, 2002.
25. L. Wang and Z.-M. Li. Approximation algorithm for a bottleneck k-Steiner tree problem in the Euclidean plane. Information Processing Letters, 81:151--156, 2002.

Index Terms

• Theory of computation

  • Randomness, geometry and discrete structures

    • Computational geometry