{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2023,10,25]],"date-time":"2023-10-25T08:48:38Z","timestamp":1698223718976},"reference-count":13,"publisher":"Wiley","issue":"8","license":[{"start":{"date-parts":[[2006,10,11]],"date-time":"2006-10-11T00:00:00Z","timestamp":1160524800000},"content-version":"vor","delay-in-days":4332,"URL":"http:\/\/onlinelibrary.wiley.com\/termsAndConditions#vor"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Networks"],"published-print":{"date-parts":[[1994,12]]},"abstract":"Abstract<\/jats:title>We experimentally evaluate sequential and distributed implementations of an approximation partitioning algorithm by Kalpakis and Sherman for the Geometric Steiner Minimum Tree Problem (GSMT)<\/jats:italic> in Rd<\/jats:sup><\/jats:italic> for d<\/jats:italic> = 2,3. Our implementations incorporate an improved method for combining the subproblems, and single\u2010and double\u2010edge reduction techniques to eliminate unnecessary Steiner points created by the partitioning process. Results show that these refinements are crucial in practice to produce high\u2010quality results. Moreover, with these refinements, the partitioning algorithm is an effective practical heuristic, which in less time finds solutions roughly comparable with those computed by Smith's Algorithm. The partitioning algorithm depends on a parameter t<\/jats:italic> through which the user can trade off time for solution quality. To solve each of the subproblems of size at most t<\/jats:italic>, we apply Smith's Algorithm, the only other Steiner tree algorithm known for R<\/jats:italic>3<\/jats:sup> under the Euclidean norm. Using uniformly generated point sets in the d<\/jats:italic>\u2010cube [0, 100]d<\/jats:sup>, we compare the running time and solution quality for the partitioning algorithm for various values of t<\/jats:italic> against that of Smith's Algorithm applied to the entire input. We also estimate the constant factor in the 1 + O(t\u22121\/d(d\u20101)<\/jats:sup>)<\/jats:italic> asymptotic performance bound proven by Kalpakis and Sherman and find that it is less than one. With d<\/jats:italic> = 2 on input sets of 25 points, our sequential implementation with t<\/jats:italic> = 7 typically found within 6 seconds a Steiner tree within 1% of the cost (342) of that computed by Smith's Algorithm in 20 seconds. At t<\/jats:italic> = 13 and using approximately 15 seconds, our sequential implementation typically found Steiner trees within 0.1% of this cost. Similarly, with d<\/jats:italic> = 3 on input sets of 60 points, our distributed implementation with t<\/jats:italic> = 10 typically found within 22 seconds a Steiner tree within 1% of the cost (1059) of that computed by Smith's Algorithm in 200 seconds. At t<\/jats:italic> = 31 and using approximately 108 seconds, our distributed implementation usually found slightly better Steiner trees than did Smith's Algorithm. \u00a9 1994 by John Wiley & Sons, Inc.<\/jats:p>","DOI":"10.1002\/net.3230240802","type":"journal-article","created":{"date-parts":[[2007,5,12]],"date-time":"2007-05-12T19:18:31Z","timestamp":1178997511000},"page":"409-415","source":"Crossref","is-referenced-by-count":6,"title":["Experimental evaluation of a partitioning algorithm for the steiner tree problem in R<\/i>2<\/sup> and R<\/i>3<\/sup>"],"prefix":"10.1002","volume":"24","author":[{"given":"Sivakumar","family":"Ravada","sequence":"first","affiliation":[]},{"given":"Alan T.","family":"Sherman","sequence":"additional","affiliation":[]}],"member":"311","published-online":{"date-parts":[[2006,10,11]]},"reference":[{"key":"e_1_2_1_2_2","doi-asserted-by":"publisher","DOI":"10.1002\/net.3230170107"},{"key":"e_1_2_1_3_2","doi-asserted-by":"publisher","DOI":"10.1145\/355759.355764"},{"key":"e_1_2_1_4_2","doi-asserted-by":"publisher","DOI":"10.1007\/BF01758759"},{"key":"e_1_2_1_5_2","first-page":"53","volume-title":"Combinatorics","author":"Cockayne E. J.","year":"1972"},{"key":"e_1_2_1_6_2","volume-title":"Introduction to Algorithms","author":"Cormen T. H.","year":"1990"},{"key":"e_1_2_1_7_2","doi-asserted-by":"publisher","DOI":"10.1002\/net.3230240303"},{"key":"e_1_2_1_8_2","first-page":"553","volume-title":"Probabilistic analysis of an enhanced partitioning algorithm for the Steiner tree problem in Rd. Proceedings of the 13th Annual Allerton Conference on Communication, Control, and Computing","author":"Kalpakis K.","year":"1992"},{"key":"e_1_2_1_9_2","doi-asserted-by":"publisher","DOI":"10.4153\/CMB-1961-016-2"},{"key":"e_1_2_1_10_2","doi-asserted-by":"publisher","DOI":"10.1002\/net.3230110104"},{"key":"e_1_2_1_11_2","doi-asserted-by":"publisher","DOI":"10.1007\/BF01758756"},{"key":"e_1_2_1_12_2","doi-asserted-by":"publisher","DOI":"10.1137\/0150015"},{"key":"e_1_2_1_13_2","doi-asserted-by":"publisher","DOI":"10.1002\/net.3230150305"},{"key":"e_1_2_1_14_2","doi-asserted-by":"publisher","DOI":"10.1002\/net.3230170203"}],"container-title":["Networks"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/api.wiley.com\/onlinelibrary\/tdm\/v1\/articles\/10.1002%2Fnet.3230240802","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/pdf\/10.1002\/net.3230240802","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,10,24]],"date-time":"2023-10-24T03:22:51Z","timestamp":1698117771000},"score":1,"resource":{"primary":{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/10.1002\/net.3230240802"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1994,12]]},"references-count":13,"journal-issue":{"issue":"8","published-print":{"date-parts":[[1994,12]]}},"alternative-id":["10.1002\/net.3230240802"],"URL":"https:\/\/doi.org\/10.1002\/net.3230240802","archive":["Portico"],"relation":{},"ISSN":["0028-3045","1097-0037"],"issn-type":[{"value":"0028-3045","type":"print"},{"value":"1097-0037","type":"electronic"}],"subject":[],"published":{"date-parts":[[1994,12]]}}}