TY - JOUR
T1 - An approximation scheme for some Steiner tree problems in the plane
AU - Wang, Lusheng
AU - Jiang, Tao
PY - 1996/12
Y1 - 1996/12
N2 - 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.
AB - 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.
UR - http://www.scopus.com/inward/record.url?scp=0038971681&partnerID=8YFLogxK
UR - https://www.scopus.com/record/pubmetrics.uri?eid=2-s2.0-0038971681&origin=recordpage
U2 - 10.1002/(SICI)1097-0037(199612)28:4<187::AID-NET3>3.0.CO;2-H
DO - 10.1002/(SICI)1097-0037(199612)28:4<187::AID-NET3>3.0.CO;2-H
M3 - 21_Publication in refereed journal
VL - 28
SP - 187
EP - 193
JO - Networks
JF - Networks
SN - 0028-3045
IS - 4
ER -