{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,12]],"date-time":"2025-10-12T04:57:08Z","timestamp":1760245028259,"version":"3.33.0"},"reference-count":23,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[1995,9,1]],"date-time":"1995-09-01T00:00:00Z","timestamp":809913600000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Discrete & Computational Geometry"],"published-print":{"date-parts":[[1995,9]]},"DOI":"10.1007\/bf02570700","type":"journal-article","created":{"date-parts":[[2007,4,28]],"date-time":"2007-04-28T04:22:00Z","timestamp":1177734120000},"page":"151-165","source":"Crossref","is-referenced-by-count":45,"title":["Low-degree minimum spanning trees"],"prefix":"10.1007","volume":"14","author":[{"given":"G.","family":"Robins","sequence":"first","affiliation":[]},{"given":"J. S.","family":"Salowe","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2005,9,1]]},"reference":[{"key":"BF02570700_CR1","doi-asserted-by":"crossref","unstructured":"T. Barrera, J. Griffith, S. A. McKee, G. Robins, and T. Zhang, Toward a Steiner Engine: Enhanced Serial and Parallel Implementations of the Iterated 1-Steiner Algorithm,Proc. Great Lakes Symp. VLSI, Kalamazoo, MI, March 1993, pp. 90\u201394.","DOI":"10.1109\/GLSV.1993.224473"},{"key":"BF02570700_CR2","doi-asserted-by":"crossref","unstructured":"T. Barrera, J. Griffith, G. Robins, and T. Zhang, Narrowing the Gap: Near-Optimal Steiner Trees in Polynomial Time,Proc. IEEE Internat. ASIC Conf. Rochester, NY, September 1993, pp. 87\u201390.","DOI":"10.1109\/ASIC.1993.410814"},{"key":"BF02570700_CR3","doi-asserted-by":"crossref","first-page":"201","DOI":"10.1007\/978-3-642-46908-4_23","volume-title":"Topics in Combinatorics and Graph Theory","author":"D. Cieslik","year":"1990","unstructured":"D. Cieslik, The Vertex Degree of Steiner Minimal Trees in Minkowski Planes, inTopics in Combinatorics and Graph Theory, R. Bodendieck and R. Henn (eds.), Physics-Verlag, Heidelberg, 1990, pp. 201\u2013206."},{"key":"BF02570700_CR4","volume-title":"Introduction to Algorithms","author":"T. H. Cormen","year":"1990","unstructured":"T. H. Cormen, C. E. Leiserson and R. Rivest,Introduction to Algorithms, MIT Press, Cambridge, MA, 1990."},{"key":"BF02570700_CR5","doi-asserted-by":"crossref","DOI":"10.1007\/978-1-4612-0963-8","volume-title":"Unsolved Problems in Geometry","author":"J. T. Croft","year":"1991","unstructured":"J. T. Croft, K. J. Falconer, and R. K. Guy,Unsolved Problems in Geometry, Springer-Verlag, New York, 1991."},{"key":"BF02570700_CR6","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1007\/BF01890113","volume":"1","author":"W. H. E. Day","year":"1984","unstructured":"W. H. E. Day and H. Edelsbrunner, Efficient Algorithms for Agglomerative Hierarchical Clustering Methods,J. Classification,1 (1984), 1\u201324.","journal-title":"J. Classification"},{"key":"BF02570700_CR7","volume-title":"Computers and Intractability: a Guide to the Theory of NP Completeness","author":"M. R. Garey","year":"1979","unstructured":"M. R. Garey and D. S. Johnson,Computers and Intractability: a Guide to the Theory of NP Completeness, Freeman, San Francisco, CA, 1979."},{"key":"BF02570700_CR8","doi-asserted-by":"crossref","first-page":"122","DOI":"10.1016\/0196-6774(87)90032-0","volume":"8","author":"G. Georgakopoulos","year":"1987","unstructured":"G. Georgakopoulos and C. H. Papadimitriou, The 1-Steiner Tree Problem,J. Algorithms,8 (1987), 122\u2013130.","journal-title":"J. Algorithms"},{"key":"BF02570700_CR9","doi-asserted-by":"crossref","first-page":"43","DOI":"10.1109\/MAHC.1985.10011","volume":"7","author":"R. L. Graham","year":"1985","unstructured":"R. L. Graham and P. Hell, On the History of the Minimum Spanning Tree Problem,Ann. of History Comput.,7 (1985), 43\u201357.","journal-title":"Ann. of History Comput."},{"key":"BF02570700_CR10","doi-asserted-by":"crossref","first-page":"219","DOI":"10.1016\/0020-0190(83)90045-5","volume":"17","author":"L. J. Guibas","year":"1983","unstructured":"L. J. Guibas and J. Stolfi, On Computing all North-East Nearest Neighbors in the L1 Metric,Inform. Process. Lett.,17 (1983), 219\u2013223.","journal-title":"Inform. Process. Lett."},{"key":"BF02570700_CR11","doi-asserted-by":"crossref","DOI":"10.1017\/CBO9780511666384","volume-title":"Three-Dimensional Integrated Circuit Layout","author":"A. C. Harter","year":"1991","unstructured":"A. C. Harter,Three-Dimensional Integrated Circuit Layout, Cambridge University Press, New York, 1991."},{"key":"BF02570700_CR12","doi-asserted-by":"crossref","first-page":"185","DOI":"10.1109\/43.46785","volume":"9","author":"J.-M. Ho","year":"1990","unstructured":"J.-M. Ho, G. Vijayan, and C. K. Wong, New Algorithms for the Rectilinear Steiner Tree Problem,IEEE Trans. Computer-Aided Design,9 (1990), 185\u2013193.","journal-title":"IEEE Trans. Computer-Aided Design"},{"key":"BF02570700_CR13","first-page":"1","volume":"14","author":"G. A. Kabatjansky","year":"1978","unstructured":"G. A. Kabatjansky and V. Leven\u015dte\u00een, Bounds for Packings of the Sphere and in Space,Problems Inform. Transmission,14 (1978) 1\u201317.","journal-title":"Problems Inform. Transmission"},{"key":"BF02570700_CR14","doi-asserted-by":"crossref","first-page":"893","DOI":"10.1109\/43.144853","volume":"11","author":"A. B. Kahng","year":"1992","unstructured":"A. B. Kahng and G. Robins, A New Class of Iterative Steiner Tree Heuristics with Good Performance,IEEE Trans. Computer-Aided Design,11 (1992), 893\u2013902.","journal-title":"IEEE Trans. Computer-Aided Design"},{"key":"BF02570700_CR15","doi-asserted-by":"crossref","first-page":"48","DOI":"10.1090\/S0002-9939-1956-0078686-7","volume":"7","author":"M. Kruskal","year":"1956","unstructured":"M. Kruskal, On the Shortest Spanning Subtree of a Graph, and the Traveling Salesman Problem,Proc. Amer. Math. Soc.,7 (1956), 48\u201350.","journal-title":"Proc. Amer. Math. Soc."},{"key":"BF02570700_CR16","doi-asserted-by":"crossref","first-page":"265","DOI":"10.1007\/BF02293049","volume":"8","author":"C. Monma","year":"1992","unstructured":"C. Monma and S. Suri, Transitions in Geometric Minimum Spanning Trees,Discrete Comput. Geom.,8 (1992), 265\u2013293.","journal-title":"Discrete Comput. Geom."},{"key":"BF02570700_CR17","doi-asserted-by":"crossref","first-page":"231","DOI":"10.1016\/0196-6774(84)90029-4","volume":"5","author":"C. H. Papadimitriou","year":"1984","unstructured":"C. H. Papadimitriou and U. V. Vazirani, On Two Geometric Problems Relating to the Traveling Salesman Problem,J. Algorithms,5 (1984), 231\u2013246.","journal-title":"J. Algorithms"},{"key":"BF02570700_CR18","volume-title":"Physical Design Automation of VLSI Systems","author":"B. T. Preas","year":"1988","unstructured":"B. T. Preas and M. J. Lorenzetti,Physical Design Automation of VLSI Systems, Benjamin\/Cummings, Menlo Park, CA, 1988."},{"key":"BF02570700_CR19","doi-asserted-by":"crossref","first-page":"1389","DOI":"10.1002\/j.1538-7305.1957.tb01515.x","volume":"36","author":"A. Prim","year":"1957","unstructured":"A. Prim, Shortest Connecting Networks and Some Generalizations,Bell Systems Tech. J.,36 (1957), 1389\u20131401.","journal-title":"Bell Systems Tech. J."},{"key":"BF02570700_CR20","doi-asserted-by":"crossref","unstructured":"G. Robins and J. S. Salowe, On the Maximum Degree of Minimum Spanning Trees,Proc. ACM Symp. Computational Geometry, Stony Brook, NY, June 1994, pp. 250\u2013258.","DOI":"10.1145\/177424.177978"},{"key":"BF02570700_CR21","doi-asserted-by":"crossref","unstructured":"J. S. Salowe and D. M. Warme, An Exact Rectilinear Steiner Tree Algorithm,Proc. IEEE Internat. Conf. Computer Design, Cambridge, MA, October 1993, pp. 472\u2013475.","DOI":"10.1109\/ICCD.1993.393331"},{"key":"BF02570700_CR22","doi-asserted-by":"crossref","unstructured":"G. F. T\u00f3th,New Results in the Theory of Packing and Covering, Convexity and its Applications 1983.","DOI":"10.1007\/978-3-0348-5858-8_14"},{"key":"BF02570700_CR23","first-page":"1061","volume":"44","author":"A. D. Wyner","year":"1965","unstructured":"A. D. Wyner, Capabilities of Bounded Discrepancy Decoding,AT & T Tech. J.,44 (1965), 1061\u20131122.","journal-title":"AT & T Tech. J."}],"container-title":["Discrete & Computational Geometry"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF02570700.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/BF02570700\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF02570700","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,1,15]],"date-time":"2025-01-15T23:18:55Z","timestamp":1736983135000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/BF02570700"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1995,9]]},"references-count":23,"journal-issue":{"issue":"2","published-print":{"date-parts":[[1995,9]]}},"alternative-id":["BF02570700"],"URL":"https:\/\/doi.org\/10.1007\/bf02570700","relation":{},"ISSN":["0179-5376","1432-0444"],"issn-type":[{"type":"print","value":"0179-5376"},{"type":"electronic","value":"1432-0444"}],"subject":[],"published":{"date-parts":[[1995,9]]}}}