Approximations for Steiner trees with minimum number of Steiner points

Donghui Chen; Ding-Zhu Du; Xiao-Dong Hu; Guo-Hui Lin; Lusheng Wang; Guoliang Xue

doi:10.1016/S0304-3975(00)00182-1

Author(s)

Donghui Chen
Ding-Zhu Du
Xiao-Dong Hu
Guo-Hui Lin
Guoliang Xue

Related Research Unit(s)

Department of Computer Science

Detail(s)

Original language	English
Pages (from-to)	83-99
Journal / Publication	Theoretical Computer Science
Volume	262
Issue number	1-2
Publication status	Published - 6 Jul 2001

Link(s)

DOI	DOI https://doi.org/10.1016/S0304-3975(00)00182-1 Final Published version
	Check@CityULib
Link to Scopus	https://www.scopus.com/record/display.uri?eid=2-s2.0-0034911862&origin=recordpage
Permanent Link	https://scholars.cityu.edu.hk/en/publications/publication(471d58a2-0531-4d49-baf4-385d25566bb0).html

Abstract

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.

Research Area(s)

Approximation algorithms, Steiner trees, VLSI design, WDM optical networks

Citation Format(s)

[ RIS ] [ BibTeX ]

Approximations for Steiner trees with minimum number of Steiner points. / Chen, Donghui; Du, Ding-Zhu; Hu, Xiao-Dong et al.
In: Theoretical Computer Science, Vol. 262, No. 1-2, 06.07.2001, p. 83-99.

Research output: Journal Publications and Reviews (RGC: 21, 22, 62) › 21_Publication in refereed journal › peer-review

Chen, D, Du, D-Z, Hu, X-D, Lin, G-H, Wang, L & Xue, G 2001, 'Approximations for Steiner trees with minimum number of Steiner points', Theoretical Computer Science, vol. 262, no. 1-2, pp. 83-99. https://doi.org/10.1016/S0304-3975(00)00182-1

Chen, D., Du, D-Z., Hu, X-D., Lin, G-H., Wang, L., & Xue, G. (2001). Approximations for Steiner trees with minimum number of Steiner points. Theoretical Computer Science, 262(1-2), 83-99. https://doi.org/10.1016/S0304-3975(00)00182-1

Chen D, Du D-Z, Hu X-D, Lin G-H, Wang L, Xue G. Approximations for Steiner trees with minimum number of Steiner points. Theoretical Computer Science. 2001 Jul 6;262(1-2):83-99. doi: 10.1016/S0304-3975(00)00182-1

Chen, Donghui ; Du, Ding-Zhu ; Hu, Xiao-Dong et al. / Approximations for Steiner trees with minimum number of Steiner points. In: Theoretical Computer Science. 2001 ; Vol. 262, No. 1-2. pp. 83-99.