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

Lusheng Wang; Zimao Li

doi:10.1016/S0020-0190(01)00209-5

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

Lusheng Wang
, Zimao Li

Department of Computer Science

Research output: Journal Publications and Reviews › RGC 21 - Publication in refereed journal › peer-review

30 Citations (Scopus)

Abstract

We study a bottleneck Steiner tree problem: given a set P = {p₁, p₂,..., 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 approximation algorithm for the problem. © 2002 Elsevier Science B.V. All rights reserved.

Original language	English
Pages (from-to)	151-156
Journal	Information Processing Letters
Volume	81
Issue number	3
DOIs	https://doi.org/10.1016/S0020-0190(01)00209-5
Publication status	Published - 14 Feb 2002

Research Keywords

Algorithmical approximation
Algorithms
Steiner trees

Access Output

10.1016/S0020-0190(01)00209-5

Other Access Options

Check CityUHK Library

Permanent Link

Right click to copy link

Cite this

@article{27544514a8f14dcc8472fd06975de792,

title = "An approximation algorithm for a bottleneck k-Steiner tree problem in the Euclidean plane",

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. {\textcopyright} 2002 Elsevier Science B.V. All rights reserved.",

keywords = "Algorithmical approximation, Algorithms, Steiner trees",

author = "Lusheng Wang and Zimao Li",

year = "2002",

month = feb,

day = "14",

doi = "10.1016/S0020-0190(01)00209-5",

language = "English",

volume = "81",

pages = "151--156",

journal = "Information Processing Letters",

issn = "0020-0190",

publisher = "Elsevier B.V.",

number = "3",

}

TY - JOUR

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

AU - Wang, Lusheng

AU - Li, Zimao

PY - 2002/2/14

Y1 - 2002/2/14

N2 - 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.

AB - 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.

KW - Algorithmical approximation

KW - Algorithms

KW - Steiner trees

UR - https://www.scopus.com/pages/publications/0037074664

UR - https://www.scopus.com/record/pubmetrics.uri?eid=2-s2.0-0037074664&origin=recordpage

U2 - 10.1016/S0020-0190(01)00209-5

DO - 10.1016/S0020-0190(01)00209-5

M3 - RGC 21 - Publication in refereed journal

SN - 0020-0190

VL - 81

SP - 151

EP - 156

JO - Information Processing Letters

JF - Information Processing Letters

IS - 3

ER -

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

Abstract

Research Keywords

Access Output

Other Access Options

Permanent Link

Other Files and Links

Fingerprint

Cite this