Approximations for Steiner Trees with Minimum Number of Steiner Points
Research output: Journal Publications and Reviews › RGC 21 - Publication in refereed journal › peer-review
Author(s)
Related Research Unit(s)
Detail(s)
| Original language | English |
|---|---|
| Pages (from-to) | 17-33 |
| Journal / Publication | Journal of Global Optimization |
| Volume | 18 |
| Issue number | 1 |
| Publication status | Published - Sept 2000 |
Link(s)
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)
Approximations for Steiner Trees with Minimum Number of Steiner Points. / CHEN, DONGHUI; DU, DING-ZHU; HU, XIAO-DONG et al.
In: Journal of Global Optimization, Vol. 18, No. 1, 09.2000, p. 17-33.
In: Journal of Global Optimization, Vol. 18, No. 1, 09.2000, p. 17-33.
Research output: Journal Publications and Reviews › RGC 21 - Publication in refereed journal › peer-review
