請用此 Handle URI 來引用此文件: http://hdl.handle.net/11455/38490
標題: An O(n log n) Heuristic Algorithm for the Rectilinear Steiner Minimal Tree Problem
作者: J.M.Smith
D.T.Lee
J.S.Liebman
摘要: This paper presents an 0 (n log n) heuristic algorithm for the Rectilinear Steiner Minimal Tree (RSMT) problem. The algorithm is based on a decomposition approach which first partitions the vertex set into triangles via the L1 Delaunay triangulation, then constructs the Steiner minimal tree according to the properties of the Voronoi diagram and the Minimum Spanning Tree (MST) of the point set. The algorithm was implemented in FORTRAN-IV and tested on a number of randomly generated point sets in the plane drawn from a uniform distribution. Comparison of the 0 (n log n) algorithms with 0 (n4) algorithms indicates that the 0 (n log n) algorithm achieves equally good reductions over the MST although the 0 (n4) algorithms actually examine more potential Steiner points and RSMT configurations.
URI: http://hdl.handle.net/11455/38490
顯示於類別:資訊科學與工程學系所

文件中的檔案:
沒有與此文件相關的檔案。


在 DSpace 系統中的文件,除了特別指名其著作權條款之外,均受到著作權保護,並且保留所有的權利。