An approximation algorithm for a bottleneck k-Steiner tree problem in the Euclidean plane

Research output: Journal Publications and Reviews (RGC: 21, 22, 62)21_Publication in refereed journalpeer-review

27 Scopus Citations
View graph of relations


Related Research Unit(s)


Original languageEnglish
Pages (from-to)151-156
Journal / PublicationInformation Processing Letters
Issue number3
Publication statusPublished - 14 Feb 2002


We study a bottleneck Steiner tree problem: given a set P = {p1, p2,..., pn} of n terminals in the Euclidean plane and a positive integer k, find a Steiner tree with at most k Steiner points such that the length of the longest edges in the tree is minimized. The problem has applications in the design of wireless communication networks. We give a ratio-1.866 approximation algorithm for the problem. © 2002 Elsevier Science B.V. All rights reserved.

Research Area(s)

  • Algorithmical approximation, Algorithms, Steiner trees