An approximation scheme for some Steiner tree problems in the plane

Research output: Journal Publications and ReviewsRGC 21 - Publication in refereed journalpeer-review

14 Scopus Citations
View graph of relations

Author(s)

Detail(s)

Original languageEnglish
Pages (from-to)187-193
Journal / PublicationNetworks
Volume28
Issue number4
Publication statusPublished - Dec 1996
Externally publishedYes

Abstract

We design a polynomial-time approximation scheme for the Steiner tree problem in the plane when the given set of regular points is c-local, i.e., in the minimum-cost spanning tree for the given set of regular points, the length of the longest edge is at most c times the length of the shortest edge. The algorithm works for both Euclidean and rectilinear metrics. For a fixed number k, the performance ratio of our algorithm is 1 + (35c/√3k) for the Euclidean metric and 1 + (9c/k) for the rectilinear metric. Thus, when k increases, the performance ratio approaches 1.

Citation Format(s)

An approximation scheme for some Steiner tree problems in the plane. / Wang, Lusheng; Jiang, Tao.
In: Networks, Vol. 28, No. 4, 12.1996, p. 187-193.

Research output: Journal Publications and ReviewsRGC 21 - Publication in refereed journalpeer-review