Premium
An approximation scheme for some Steiner tree problems in the plane
Author(s) -
Wang Lusheng,
Jiang Tao
Publication year - 1996
Publication title -
networks
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.977
H-Index - 64
eISSN - 1097-0037
pISSN - 0028-3045
DOI - 10.1002/(sici)1097-0037(199612)28:4<187::aid-net3>3.0.co;2-h
Subject(s) - steiner tree problem , scheme (mathematics) , tree (set theory) , mathematics , plane (geometry) , combinatorics , computer science , mathematical optimization , geometry , mathematical analysis
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 + (35 c /&3 k square;) for the Euclidean metric and 1 + (9 c/k ) for the rectilinear metric. Thus, when k increases, the performance ratio approaches 1. © 1996 John Wiley & Sons, Inc.