Please use this identifier to cite or link to this item:
標題: An O(n log n) Heuristic Algorithm for the Rectilinear Steiner Minimal Tree Problem
作者: J.M.Smith
Project: Engineering Optimization, Volume�4, Issue�4, Page(s) �179-192.
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.
DOI: 10.1080/03052158008902421
Appears in Collections:資訊科學與工程學系所

Show full item record

Google ScholarTM




Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.