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

Authors
Wang, LS Li, ZM
Citation
Ls. Wang et Zm. Li, An approximation algorithm for a bottleneck k-Steiner tree problem in the Euclidean plane, INF PROCESS, 81(3), 2002, pp. 151-156
Citations number
7
Categorie Soggetti
Information Tecnology & Communication Systems
Journal title
INFORMATION PROCESSING LETTERS
ISSN journal
00200190 → ACNP
Volume
81
Issue
3
Year of publication
2002
Pages
151 - 156
Database
ISI
SICI code
0020-0190(20020214)81:3<151:AAAFAB>2.0.ZU;2-A
Abstract
We study a bottleneck Steiner tree problem: given a set P = {p(1,) p(2), - - -, p(n) } 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 appro ximation algorithm for the problem. (C) 2002 Elsevier Science B.V. All righ ts reserved.