We use cookies to improve your experience with our site.
MA Jun, YANG Bo, MA Shaohan. A Practical Algorithm for the Minimum Rectilinear Steiner Tree[J]. Journal of Computer Science and Technology, 2000, 15(1): 96-99.
Citation:
MA Jun, YANG Bo, MA Shaohan. A Practical Algorithm for the Minimum Rectilinear Steiner Tree[J]. Journal of Computer Science and Technology, 2000, 15(1): 96-99.
MA Jun, YANG Bo, MA Shaohan. A Practical Algorithm for the Minimum Rectilinear Steiner Tree[J]. Journal of Computer Science and Technology, 2000, 15(1): 96-99.
Citation:
MA Jun, YANG Bo, MA Shaohan. A Practical Algorithm for the Minimum Rectilinear Steiner Tree[J]. Journal of Computer Science and Technology, 2000, 15(1): 96-99.
A Practical Algorithm for the Minimum Rectilinear Steiner Tree
An O(n2) time approximation algorithm for the minimum rectilinear Steiner tree is proposed. The approximation ratio of the algorithm is strictlyless than 1.5. The computing performances show the costs of the spanning treesproduced by the algorithm are only 0.8% away from the optimal ones.
DownLoad: