An efficient approximation algorithm for the Steiner tree problem in rectilinear graphs

For a given set A of points in a grid graph G with all edges being of weight l, the problem of determining the tree that interconnects all the points in A under the minimum total weight is the rectilinear Steiner tree problem. For this problem, a new approximation algorithm that makes use of the uniformity in structure of the rectilinear graphs is proposed. A Steiner tree is obtained from the minimal tree on the Delaunay net by means of the interval graphs. When k (n, resp.) indicates the number of points (nodes, resp). of A (G, resp.), in general being k⩽n, the complexity of this method does not depend on n, this method is valid for large n. On average, an approximate solution with small weight can be obtained