{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,8,29]],"date-time":"2025-08-29T10:22:00Z","timestamp":1756462920587},"reference-count":25,"publisher":"Wiley","issue":"1","license":[{"start":{"date-parts":[[2006,10,11]],"date-time":"2006-10-11T00:00:00Z","timestamp":1160524800000},"content-version":"vor","delay-in-days":9355,"URL":"http:\/\/onlinelibrary.wiley.com\/termsAndConditions#vor"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Networks"],"published-print":{"date-parts":[[1981,3]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>An <jats:italic>O<\/jats:italic>(<jats:italic>n<\/jats:italic> log <jats:italic>n<\/jats:italic>) 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 \u201crecomposes\u201d 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\u2010IV and tested on a number of randomly generated point sets in the plane drawn from a uniform distribution. Comparison of the <jats:italic>O<\/jats:italic>(<jats:italic>n<\/jats:italic> log <jats:italic>n<\/jats:italic>) algorithm with an <jats:italic>O<\/jats:italic>(<jats:italic>n<\/jats:italic><jats:sup>4<\/jats:sup>) algorithm clearly indicates that the <jats:italic>O<\/jats:italic>(<jats:italic>n<\/jats:italic> log <jats:italic>n<\/jats:italic>) algorithm is as good as the previous <jats:italic>O<\/jats:italic>(<jats:italic>n<\/jats:italic><jats:sup>4<\/jats:sup>) algorithm in achieving reductions in the ratio SMT\/MST of the given vertex set. This is somewhat surprising since the <jats:italic>O<\/jats:italic>(<jats:italic>n<\/jats:italic><jats:sup>4<\/jats:sup>) algorithm considers more potential Steiner points and alternative tree configurations.<\/jats:p>","DOI":"10.1002\/net.3230110104","type":"journal-article","created":{"date-parts":[[2007,5,11]],"date-time":"2007-05-11T11:47:02Z","timestamp":1178884022000},"page":"23-39","source":"Crossref","is-referenced-by-count":74,"title":["An O(<i>n<\/i> log <i>n<\/i>) heuristic for steiner minimal tree problems on the euclidean metric"],"prefix":"10.1002","volume":"11","author":[{"given":"J. Macgregor","family":"Smith","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"D. T.","family":"Lee","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Judith S.","family":"Liebman","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"311","published-online":{"date-parts":[[2006,10,11]]},"reference":[{"key":"e_1_2_1_2_2","volume-title":"The Design and Analysis of Computer Algorithms","author":"Aho A. H.","year":"1974"},{"key":"e_1_2_1_3_2","doi-asserted-by":"publisher","DOI":"10.1145\/321724.321733"},{"key":"e_1_2_1_4_2","doi-asserted-by":"publisher","DOI":"10.1137\/0134003"},{"key":"e_1_2_1_5_2","doi-asserted-by":"publisher","DOI":"10.1137\/0205051"},{"key":"e_1_2_1_6_2","volume-title":"What Is Mathematics","author":"Courant D. R.","year":"1941"},{"key":"e_1_2_1_7_2","unstructured":"R.DrysdaleandD. T.Lee \u201cGeneralized Voronoi Diagram in the Plane \u201d Proc. 16th Allerton Conference on Comm. Control and Computing (1978) pp.833\u2013842."},{"key":"e_1_2_1_8_2","doi-asserted-by":"publisher","DOI":"10.1137\/0132072"},{"key":"e_1_2_1_9_2","doi-asserted-by":"publisher","DOI":"10.1137\/0116001"},{"key":"e_1_2_1_10_2","first-page":"177","article-title":"Remarks on Steiner Minimal Trees I","volume":"4","author":"Graham R. L.","year":"1976","journal-title":"Bull. Inst. Math. Acad. Sinica"},{"key":"e_1_2_1_11_2","doi-asserted-by":"publisher","DOI":"10.1109\/TCS.1979.1084551"},{"key":"e_1_2_1_12_2","first-page":"303","article-title":"The Rectilinear Steiner Problem","volume":"2","author":"Hwang F. K.","year":"1978","journal-title":"J. Design Auto. Fault Toler. Anal."},{"key":"e_1_2_1_13_2","doi-asserted-by":"publisher","DOI":"10.1287\/moor.2.3.209"},{"key":"e_1_2_1_14_2","doi-asserted-by":"publisher","DOI":"10.1007\/BF01584648"},{"key":"e_1_2_1_15_2","volume-title":"Studies in Mathematics","author":"Kuhn H. W.","year":"1975"},{"key":"e_1_2_1_16_2","volume-title":"On Finding k Nearest Neighbors in the Plane","author":"Lee D. T.","year":"1976"},{"key":"e_1_2_1_17_2","unstructured":"D. T.Lee \u201cGeneralization of Voronoi Diagrams \u201d Extended abstract Coordinated Science Laboratory University of Illinois (unpublished)."},{"key":"e_1_2_1_18_2","doi-asserted-by":"publisher","DOI":"10.4153\/CMB-1961-016-2"},{"key":"e_1_2_1_19_2","volume-title":"Companion to Concrete Mathematics","author":"Melzak Z. A.","year":"1973"},{"key":"e_1_2_1_20_2","volume-title":"Mathematical Ideas, Modeling, and Applications","author":"Melzak Z. A.","year":"1976"},{"key":"e_1_2_1_21_2","doi-asserted-by":"publisher","DOI":"10.1287\/opre.6.2.232"},{"key":"e_1_2_1_22_2","doi-asserted-by":"publisher","DOI":"10.1016\/0097-3165(78)90058-4"},{"key":"e_1_2_1_23_2","doi-asserted-by":"crossref","unstructured":"M. I.Shamos \u201cGeometric Complexity \u201d Seventh Annual ACM SIGACT Conference 1975 pp.224\u2013233.","DOI":"10.1145\/800116.803772"},{"key":"e_1_2_1_24_2","unstructured":"M. I.Shamos \u201cComputational Geometry \u201d Ph.D. thesis Yale University 1977."},{"key":"e_1_2_1_25_2","doi-asserted-by":"publisher","DOI":"10.1080\/03052157908902401"},{"key":"e_1_2_1_26_2","unstructured":"J.MacGregor Smith \u201cAlgorithms for Generalized Steiner Network Problems \u201d Ph.D. thesis Department of Mechanical and Industrial Engineering University of Illinois 1978(unpublished)."}],"container-title":["Networks"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/api.wiley.com\/onlinelibrary\/tdm\/v1\/articles\/10.1002%2Fnet.3230110104","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/pdf\/10.1002\/net.3230110104","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,11,12]],"date-time":"2023-11-12T12:14:41Z","timestamp":1699791281000},"score":1,"resource":{"primary":{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/10.1002\/net.3230110104"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1981,3]]},"references-count":25,"journal-issue":{"issue":"1","published-print":{"date-parts":[[1981,3]]}},"alternative-id":["10.1002\/net.3230110104"],"URL":"https:\/\/doi.org\/10.1002\/net.3230110104","archive":["Portico"],"relation":{},"ISSN":["0028-3045","1097-0037"],"issn-type":[{"value":"0028-3045","type":"print"},{"value":"1097-0037","type":"electronic"}],"subject":[],"published":{"date-parts":[[1981,3]]}}}