Please use this identifier to cite or link to this item: http://hdl.handle.net/11455/38476
DC FieldValueLanguage
dc.contributor.authorJ.M.Smithen_US
dc.contributor.authorD.T.Leeen_US
dc.contributor.authorJ.S.Liebmanen_US
dc.date1981en_US
dc.date.accessioned2014-06-06T08:00:51Z-
dc.date.available2014-06-06T08:00:51Z-
dc.identifier.urihttp://hdl.handle.net/11455/38476-
dc.description.abstractAn O(n log n) heuristic for the Euclidean Steiner Minimal Tree (ESMT) problem is presented. The algorithm is based on a decomposition approach which first partitions the vertex set into triangles via the Delaunay triangulation, then “recomposes” the suboptimal Steiner Minimal Tree (SMT) according to the Voronoi diagram and Minimum Spanning Tree (MST) of the point set. The ESMT 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 O(n log n) algorithm with an O(n4) algorithm clearly indicates that the O(n log n) algorithm is as good as the previous O(n4) algorithm in achieving reductions in the ratio SMT/MST of the given vertex set. This is somewhat surprising since the O(n4) algorithm considers more potential Steiner points and alternative tree configurations.en_US
dc.language.isoen_USen_US
dc.relationNetworks, Volume�11, Issue�1, Page(s) �23-29.en_US
dc.titleAn O(n log n) Heuristic for Steiner Minimal Tree Problems on the Euclidean Metricen_US
dc.typeJournal Articlezh_TW
dc.identifier.doi10.1002/net.3230110104en_US
Appears in Collections:資訊科學與工程學系所
文件中的檔案:

取得全文請前往華藝線上圖書館



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