TY - JOUR
T1 - Approximations for Steiner trees with minimum number of Steiner points
AU - Chen, Donghui
AU - Du, Ding-Zhu
AU - Hu, Xiao-Dong
AU - Lin, Guo-Hui
AU - Wang, Lusheng
AU - Xue, Guoliang
PY - 2001/7/6
Y1 - 2001/7/6
N2 - Given n terminals in the Euclidean plane and a positive constant, find a Steiner tree interconnecting all terminals with the minimum number of Steiner points such that the Euclidean length of each edge is no more than the given positive constant. This problem is NP-hard with applications in VLSI design, WDM optical networks and wireless communications. In this paper, we show that (a) the Steiner ratio is 1/4, that is, the minimum spanning tree yields a polynomial-time approximation with performance ratio exactly 4, (b) there exists a polynomial-time approximation with performance ratio 3, and (c) there exists a polynomial-time approximation scheme under certain conditions.
AB - Given n terminals in the Euclidean plane and a positive constant, find a Steiner tree interconnecting all terminals with the minimum number of Steiner points such that the Euclidean length of each edge is no more than the given positive constant. This problem is NP-hard with applications in VLSI design, WDM optical networks and wireless communications. In this paper, we show that (a) the Steiner ratio is 1/4, that is, the minimum spanning tree yields a polynomial-time approximation with performance ratio exactly 4, (b) there exists a polynomial-time approximation with performance ratio 3, and (c) there exists a polynomial-time approximation scheme under certain conditions.
KW - Approximation algorithms
KW - Steiner trees
KW - VLSI design
KW - WDM optical networks
UR - http://www.scopus.com/inward/record.url?scp=0034911862&partnerID=8YFLogxK
UR - https://www.scopus.com/record/pubmetrics.uri?eid=2-s2.0-0034911862&origin=recordpage
U2 - 10.1016/S0304-3975(00)00182-1
DO - 10.1016/S0304-3975(00)00182-1
M3 - 21_Publication in refereed journal
VL - 262
SP - 83
EP - 99
JO - Theoretical Computer Science
JF - Theoretical Computer Science
SN - 0304-3975
IS - 1-2
ER -