{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,12]],"date-time":"2025-10-12T04:57:06Z","timestamp":1760245026004,"version":"3.33.0"},"reference-count":30,"publisher":"Wiley","issue":"2","license":[{"start":{"date-parts":[[2006,10,11]],"date-time":"2006-10-11T00:00:00Z","timestamp":1160524800000},"content-version":"vor","delay-in-days":4242,"URL":"http:\/\/onlinelibrary.wiley.com\/termsAndConditions#vor"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Networks"],"published-print":{"date-parts":[[1995,3]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>Given a set of terminals in the plane, a rectilinear Steiner minimal tree is a shortest interconnection among these terminals using only horizontal and vertical edges. We present an algorithm that constructs a rectilinear Steiner minimal tree for any input terminal set. On a workstation, problems involving 20 input terminals can be solved in a few seconds, and problems involving 30 input terminals can be solved, on average, in 30 min. Previous algorithms could only solve 16\u2010 or 17\u2010point point problems within the 30 min time bound. Problems involving 35 points can be solved, on average, within a day. Our experiments were run on uniformly distributed data on an integer grid.<\/jats:p>","DOI":"10.1002\/net.3230250206","type":"journal-article","created":{"date-parts":[[2007,5,12]],"date-time":"2007-05-12T19:21:42Z","timestamp":1178997702000},"page":"69-87","source":"Crossref","is-referenced-by-count":21,"title":["Thirty\u2010five\u2010point rectilinear steiner minimal trees in a day"],"prefix":"10.1002","volume":"25","author":[{"given":"Jeffrey S.","family":"Salowe","sequence":"first","affiliation":[]},{"given":"David M.","family":"Warme","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.3230200407"},{"key":"e_1_2_1_3_2","doi-asserted-by":"publisher","DOI":"10.1145\/322092.322095"},{"key":"e_1_2_1_4_2","doi-asserted-by":"publisher","DOI":"10.1007\/BF00149359"},{"key":"e_1_2_1_5_2","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(86)90062-1"},{"key":"e_1_2_1_6_2","doi-asserted-by":"publisher","DOI":"10.1007\/BF01758759"},{"key":"e_1_2_1_7_2","doi-asserted-by":"publisher","DOI":"10.1109\/43.45871"},{"key":"e_1_2_1_8_2","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.3240050405"},{"key":"e_1_2_1_9_2","doi-asserted-by":"publisher","DOI":"10.1137\/0204043"},{"key":"e_1_2_1_10_2","doi-asserted-by":"crossref","unstructured":"J. L.GanleyandJ. P.Cohoon A faster dynamic programming algorithm for exact rectilinear Steiner minimal trees.Fourth Great Lakes Symposium on VLSI(1994)238\u2013241.","DOI":"10.1109\/GLSV.1994.289962"},{"key":"e_1_2_1_11_2","unstructured":"J. L.GanleyandJ. P.Cohoon Optimal rectilinear Steiner minimal treesinO(n22.62n) time.Proc. 6th Can. Conf. Comput. Geom. (1994)308\u2013313."},{"key":"e_1_2_1_12_2","doi-asserted-by":"publisher","DOI":"10.1137\/0132071"},{"key":"e_1_2_1_13_2","doi-asserted-by":"publisher","DOI":"10.1016\/0196-6774(89)90011-4"},{"key":"e_1_2_1_14_2","doi-asserted-by":"publisher","DOI":"10.1137\/0114025"},{"key":"e_1_2_1_15_2","doi-asserted-by":"publisher","DOI":"10.1137\/0202012"},{"key":"e_1_2_1_16_2","doi-asserted-by":"publisher","DOI":"10.1137\/0130013"},{"key":"e_1_2_1_17_2","doi-asserted-by":"publisher","DOI":"10.1002\/net.3230220105"},{"key":"e_1_2_1_18_2","doi-asserted-by":"publisher","DOI":"10.1109\/43.144853"},{"key":"e_1_2_1_19_2","doi-asserted-by":"publisher","DOI":"10.1002\/net.3230150403"},{"key":"e_1_2_1_20_2","doi-asserted-by":"crossref","unstructured":"T.LeightonandS.Rao An approximate max\u2010flow mincut theorem for uniform multicommodity flow problems with applications to approximation algorithms.Proc. 29th IEEE Symp. Found. Comput. Sci.(1988)422\u2013431.","DOI":"10.1109\/SFCS.1988.21958"},{"key":"e_1_2_1_21_2","doi-asserted-by":"crossref","unstructured":"F. D.Lewis W. C.Pong andN.Van Cleave Optimum Steiner tree generation.Second Great Lakes Symposium on VLSI(1992)207\u2013212.","DOI":"10.1109\/GLSV.1992.218343"},{"key":"e_1_2_1_22_2","doi-asserted-by":"publisher","DOI":"10.4153\/CMB-1961-016-2"},{"key":"e_1_2_1_23_2","doi-asserted-by":"publisher","DOI":"10.1137\/0219018"},{"key":"e_1_2_1_24_2","doi-asserted-by":"publisher","DOI":"10.1007\/BF01758761"},{"key":"e_1_2_1_25_2","unstructured":"G. M.Shute A reduced grid for rectilinear Steiner minimal trees.Proc. 2nd Can. Conf. Comput. Geom. (1990)309\u2013314."},{"key":"e_1_2_1_26_2","first-page":"28","article-title":"Minimal rectilinear Steiner trees","volume":"1","author":"Sidorenko A. F.","year":"1989","journal-title":"Diskret. Mat."},{"key":"e_1_2_1_27_2","doi-asserted-by":"crossref","unstructured":"C. D.Thomborson L. L.Deneen andG. M.Shute Computing a rectilinear Steiner minimal tree in O(n\u221an) time.Parallel Algor. Architect. (1987)176\u2013183.","DOI":"10.1007\/3-540-18099-0_44"},{"key":"e_1_2_1_28_2","first-page":"119","volume-title":"Rectilinear Steiner tree minimization on a workstation, in Computational Support for Discrete Mathematics, DIMACS Series in Discrete Mathematics and Theoretical Computer Science","author":"Thomborson C. D.","year":"1994"},{"key":"e_1_2_1_29_2","doi-asserted-by":"publisher","DOI":"10.1002\/net.3230150305"},{"key":"e_1_2_1_30_2","doi-asserted-by":"publisher","DOI":"10.1002\/net.3230170203"},{"key":"e_1_2_1_31_2","unstructured":"Y. Y.YangandO.Wing Optimal and suboptimal solution algorithms for the wiring problem.Proc. IEEE Int. Symp. Circuit Theory(1972)154\u2013158."}],"container-title":["Networks"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/api.wiley.com\/onlinelibrary\/tdm\/v1\/articles\/10.1002%2Fnet.3230250206","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/pdf\/10.1002\/net.3230250206","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,1,16]],"date-time":"2025-01-16T05:55:46Z","timestamp":1737006946000},"score":1,"resource":{"primary":{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/10.1002\/net.3230250206"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1995,3]]},"references-count":30,"journal-issue":{"issue":"2","published-print":{"date-parts":[[1995,3]]}},"alternative-id":["10.1002\/net.3230250206"],"URL":"https:\/\/doi.org\/10.1002\/net.3230250206","archive":["Portico"],"relation":{},"ISSN":["0028-3045","1097-0037"],"issn-type":[{"type":"print","value":"0028-3045"},{"type":"electronic","value":"1097-0037"}],"subject":[],"published":{"date-parts":[[1995,3]]}}}