{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,11,2]],"date-time":"2025-11-02T10:22:12Z","timestamp":1762078932302},"reference-count":35,"publisher":"Wiley","issue":"4","license":[{"start":{"date-parts":[[2006,10,11]],"date-time":"2006-10-11T00:00:00Z","timestamp":1160524800000},"content-version":"vor","delay-in-days":3967,"URL":"http:\/\/onlinelibrary.wiley.com\/termsAndConditions#vor"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Networks"],"published-print":{"date-parts":[[1995,12]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>Even though the problem of computing Steiner minimal trees (SMTs) in the plane is well known to be <jats:italic>NP<\/jats:italic>\u2010hard, There exist heuristic algorithms which run in polynomial time. Recent research results have shown that the problem in three dimensions is demonstrably more difficult. This paper approaches the development of a heuristic for the problem utilizing the Delaunay triangulation in 3\u2010space to compute suboptimal SMTs. Computational results are also provided.<\/jats:p>","DOI":"10.1002\/net.3230260411","type":"journal-article","created":{"date-parts":[[2007,5,12]],"date-time":"2007-05-12T20:48:55Z","timestamp":1179002935000},"page":"273-289","source":"Crossref","is-referenced-by-count":13,"title":["An O(N<sup>2<\/sup>) heuristic for steiner minimal trees in E<sup>3<\/sup>"],"prefix":"10.1002","volume":"26","author":[{"given":"J. MacGregor","family":"Smith","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Rich","family":"Weiss","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Minoo","family":"Patel","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","doi-asserted-by":"publisher","DOI":"10.1038\/scientificamerican0189-84"},{"key":"e_1_2_1_3_2","doi-asserted-by":"publisher","DOI":"10.1142\/9789814355858_0002"},{"key":"e_1_2_1_4_2","doi-asserted-by":"publisher","DOI":"10.1016\/0377-2217(92)90214-T"},{"key":"e_1_2_1_5_2","doi-asserted-by":"publisher","DOI":"10.1002\/net.3230240404"},{"key":"e_1_2_1_6_2","volume-title":"Fast triangulation via empty spheres","author":"Beichel I.","year":"1992"},{"key":"e_1_2_1_7_2","doi-asserted-by":"publisher","DOI":"10.1145\/321724.321733"},{"key":"e_1_2_1_8_2","doi-asserted-by":"publisher","DOI":"10.1137\/0205051"},{"key":"e_1_2_1_9_2","doi-asserted-by":"publisher","DOI":"10.1016\/S0167-5060(08)70332-7"},{"key":"e_1_2_1_10_2","doi-asserted-by":"publisher","DOI":"10.1137\/0134003"},{"issue":"2","key":"e_1_2_1_11_2","first-page":"213","article-title":"Steiner's problem for set terminals","volume":"26","author":"Cockayne E. J.","year":"1968","journal-title":"J Appl. Math."},{"key":"e_1_2_1_12_2","doi-asserted-by":"publisher","DOI":"10.2307\/2688541"},{"key":"e_1_2_1_13_2","volume-title":"What Is Mathematics?","author":"Courant D. R.","year":"1941"},{"key":"e_1_2_1_14_2","doi-asserted-by":"publisher","DOI":"10.1007\/BF02067239"},{"key":"e_1_2_1_15_2","unstructured":"D. Z.Du Disproving Gilbert\u2010Pollak conjecture in higher dimensional spaces. Manuscript. Computer Science Department University of Minnesota (September1992)."},{"key":"e_1_2_1_16_2","doi-asserted-by":"publisher","DOI":"10.1007\/BF01758755"},{"key":"e_1_2_1_17_2","doi-asserted-by":"publisher","DOI":"10.2307\/1999307"},{"key":"e_1_2_1_18_2","unstructured":"D. Z.Du andW.Smith Three disproofs of the Gilbert Pollak conjecture on Steiner ratio in three or more dimensions.J. Combin. Theory Ser. A in press."},{"key":"e_1_2_1_19_2","doi-asserted-by":"publisher","DOI":"10.1142\/9789812831699_0007"},{"key":"e_1_2_1_20_2","doi-asserted-by":"publisher","DOI":"10.1137\/0132072"},{"key":"e_1_2_1_21_2","volume-title":"Computers and Intractability; A Guide to the Theory of Np\u2010completeness","author":"Garey M. R.","year":"1979"},{"key":"e_1_2_1_22_2","first-page":"177","article-title":"Remarks on Steiner minimal trees","volume":"4","author":"Graham R. L.","year":"1976","journal-title":"Bull. Inst. Math. Acad. Sin."},{"key":"e_1_2_1_23_2","doi-asserted-by":"publisher","DOI":"10.1137\/0116001"},{"key":"e_1_2_1_24_2","doi-asserted-by":"publisher","DOI":"10.1002\/net.3230220105"},{"key":"e_1_2_1_25_2","volume-title":"Ceramic Science for Materials Technologists","author":"McColm I. J.","year":"1983"},{"key":"e_1_2_1_26_2","doi-asserted-by":"publisher","DOI":"10.4153\/CMB-1961-016-2"},{"key":"e_1_2_1_27_2","doi-asserted-by":"publisher","DOI":"10.1002\/j.1538-7305.1957.tb01515.x"},{"key":"e_1_2_1_28_2","doi-asserted-by":"publisher","DOI":"10.1002\/net.3230110104"},{"key":"e_1_2_1_29_2","doi-asserted-by":"publisher","DOI":"10.1080\/03052157908902401"},{"key":"e_1_2_1_30_2","doi-asserted-by":"publisher","DOI":"10.1007\/BF01758756"},{"key":"e_1_2_1_31_2","doi-asserted-by":"publisher","DOI":"10.1016\/0097-3165(95)90055-1"},{"key":"e_1_2_1_32_2","doi-asserted-by":"publisher","DOI":"10.1007\/BF02018822"},{"key":"e_1_2_1_33_2","doi-asserted-by":"publisher","DOI":"10.1137\/0217035"},{"key":"e_1_2_1_34_2","doi-asserted-by":"publisher","DOI":"10.1007\/BF01955730"},{"key":"e_1_2_1_35_2","doi-asserted-by":"publisher","DOI":"10.1002\/net.3230170203"},{"key":"e_1_2_1_36_2","doi-asserted-by":"publisher","DOI":"10.1007\/BF01187035"}],"container-title":["Networks"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/api.wiley.com\/onlinelibrary\/tdm\/v1\/articles\/10.1002%2Fnet.3230260411","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/pdf\/10.1002\/net.3230260411","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,10,25]],"date-time":"2023-10-25T16:28:48Z","timestamp":1698251328000},"score":1,"resource":{"primary":{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/10.1002\/net.3230260411"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1995,12]]},"references-count":35,"journal-issue":{"issue":"4","published-print":{"date-parts":[[1995,12]]}},"alternative-id":["10.1002\/net.3230260411"],"URL":"https:\/\/doi.org\/10.1002\/net.3230260411","archive":["Portico"],"relation":{},"ISSN":["0028-3045","1097-0037"],"issn-type":[{"value":"0028-3045","type":"print"},{"value":"1097-0037","type":"electronic"}],"subject":[],"published":{"date-parts":[[1995,12]]}}}