论文部分内容阅读
An O(n2) time approximation algorithm for the minimum rectilinear Steiner tree is proposed. The approximation ratio of the algorithm is strictly less than 1.5. The computing performances show the costs of the spanning trees produced by the algorithm are only 0.8% away from the optimal ones.