TY - JOUR
T1 - Steiner tree problem with minimum number of Steiner points and bounded edge-length
AU - Lin, Guo Hui
AU - Xue, Guoliang
N1 - Funding Information:
* Corresponding author. Email: xue@cs.uvm.edu. The research of this author was supported in part by the Army Research Office grant DAAH@4-96-10233 and by the National Science Foundation grants ASC-9409285 and OSR-9350540. ’ Email: ghlin@cs.uvm.edu. The research of this author was supported in part by the Army Research Office grant DAAHW-96.10233, and by the Presidential Chuang Xin Foundation of the Chinese Academy of Sciences.
PY - 1999/1/29
Y1 - 1999/1/29
N2 - In this paper, we study the Steiner tree problem with minimum number of Steiner points and bounded edge-length (STP-MSPBEL), which asks for a tree interconnecting a given set of n terminal points and a minimum number of Steiner points such that the Euclidean length of each edge is no more than a given positive constant. This problem has applications in VLSI design, WDM optimal networks and wireless communications. We prove that this problem is NP-complete and present a polynomial time approximation algorithm whose worst-case performance ratio is 5.
AB - In this paper, we study the Steiner tree problem with minimum number of Steiner points and bounded edge-length (STP-MSPBEL), which asks for a tree interconnecting a given set of n terminal points and a minimum number of Steiner points such that the Euclidean length of each edge is no more than a given positive constant. This problem has applications in VLSI design, WDM optimal networks and wireless communications. We prove that this problem is NP-complete and present a polynomial time approximation algorithm whose worst-case performance ratio is 5.
KW - Algorithms
KW - Approximation algorithms
KW - Steiner minimum trees
KW - VLSI design
KW - WDM optimal networks
KW - Wireless communications
UR - http://www.scopus.com/inward/record.url?scp=0032755118&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=0032755118&partnerID=8YFLogxK
U2 - 10.1016/s0020-0190(98)00201-4
DO - 10.1016/s0020-0190(98)00201-4
M3 - Article
AN - SCOPUS:0032755118
SN - 0020-0190
VL - 69
SP - 53
EP - 57
JO - Information Processing Letters
JF - Information Processing Letters
IS - 2
ER -