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 journal › peer-review
Author(s)
Related Research Unit(s)
Detail(s)
| Original language | English |
|---|---|
| Pages (from-to) | 151-156 |
| Journal / Publication | Information Processing Letters |
| Volume | 81 |
| Issue number | 3 |
| Publication status | Published - 14 Feb 2002 |
Link(s)
Abstract
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
Citation Format(s)
An approximation algorithm for a bottleneck k-Steiner tree problem in the Euclidean plane. / Wang, Lusheng; Li, Zimao.
In: Information Processing Letters, Vol. 81, No. 3, 14.02.2002, p. 151-156.
In: Information Processing Letters, Vol. 81, No. 3, 14.02.2002, p. 151-156.
Research output: Journal Publications and Reviews (RGC: 21, 22, 62) › 21_Publication in refereed journal › peer-review
