{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,5]],"date-time":"2024-09-05T20:03:56Z","timestamp":1725566636388},"publisher-location":"Berlin, Heidelberg","reference-count":23,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540230953"},{"type":"electronic","value":"9783540302056"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2004]]},"DOI":"10.1007\/978-3-540-30205-6_46","type":"book-chapter","created":{"date-parts":[[2010,9,21]],"date-time":"2010-09-21T17:00:42Z","timestamp":1285088442000},"page":"442-452","source":"Crossref","is-referenced-by-count":3,"title":["An Efficient Low-Degree RMST Algorithm for VLSI\/ULSI Physical Design"],"prefix":"10.1007","author":[{"given":"Yin","family":"Wang","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Xianlong","family":"Hong","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Tong","family":"Jing","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Yang","family":"Yang","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Xiaodong","family":"Hu","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Guiying","family":"Yan","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"46_CR1","doi-asserted-by":"crossref","unstructured":"Barrera, T., Griffith, J., et al.: Toward a Steiner engine: Enhanced serial and parallel implementations of the iterated 1-steiner algorithm. In: Proc.GLSVLSI, MI, p. 90 (1993)","DOI":"10.1109\/GLSV.1993.224473"},{"issue":"4","key":"46_CR2","doi-asserted-by":"publisher","first-page":"724","DOI":"10.1137\/0205051","volume":"5","author":"D. Cheriton","year":"1976","unstructured":"Cheriton, D., Tarjan, R.E.: Finding minimum spanning trees. SIAM Journal on Computing\u00a05(4), 724\u2013742 (1976)","journal-title":"SIAM Journal on Computing"},{"key":"46_CR3","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"105","DOI":"10.1007\/3-540-61310-2_9","volume-title":"Integer Programming and Combinatorial Optimization","author":"S.P. Fekete","year":"1996","unstructured":"Fekete, S.P., Khuller, S., Klemmstein, M., et al.: A network-flow technique for finding lowweight bounded-degree trees. In: Cunningham, W.H., Queyranne, M., McCormick, S.T. (eds.) IPCO 1996. LNCS, vol.\u00a01084, pp. 105\u2013117. Springer, Heidelberg (1996)"},{"key":"46_CR4","doi-asserted-by":"publisher","first-page":"781","DOI":"10.1137\/0214055","volume":"14","author":"G.N. Fredrickson","year":"1985","unstructured":"Fredrickson, G.N.: Data structures for on-line updating of minimum spanning trees. SIAM Journal on Computing\u00a014, 781\u2013798 (1985)","journal-title":"SIAM Journal on Computing"},{"key":"46_CR5","volume-title":"Computers and Intractability: a Guide to the Theory of NP Completeness","author":"M.R. Garey","year":"1979","unstructured":"Garey, M.R., Johnson, D.S.: Computers and Intractability: a Guide to the Theory of NP Completeness. W.H. Freeman, New York (1979)"},{"key":"46_CR6","doi-asserted-by":"publisher","first-page":"122","DOI":"10.1016\/0196-6774(87)90032-0","volume":"8","author":"G. Georgakopoulos","year":"1987","unstructured":"Georgakopoulos, G., Papadimitriou, C.H.: The 1-steiner tree problem. Journal of Algorithms\u00a08, 122\u2013130 (1987)","journal-title":"Journal of Algorithms"},{"key":"46_CR7","doi-asserted-by":"publisher","first-page":"43","DOI":"10.1109\/MAHC.1985.10011","volume":"7","author":"R.L. Graham","year":"1985","unstructured":"Graham, R.L., Hell, P.: On the history of the minimum spanning tree problem. Annals of the History of Computing\u00a07, 43\u201357 (1985)","journal-title":"Annals of the History of Computing"},{"issue":"11","key":"46_CR8","doi-asserted-by":"crossref","first-page":"1351","DOI":"10.1109\/43.329264","volume":"13","author":"J. Griffith","year":"1994","unstructured":"Griffith, J., Robins, G., Salowe, J.S., et al.: Closing the gap: Near-optimal steiner trees in polynomial time. IEEE Trans. on CAD\u00a013(11), 1351\u20131365 (1994)","journal-title":"IEEE Trans. on CAD"},{"key":"46_CR9","doi-asserted-by":"crossref","unstructured":"Guibas, L.J., Stolfi, J.: On computing all north-east nearest neighbors in the L1 metric. Information Processing Letters\u00a017 (1983)","DOI":"10.1016\/0020-0190(83)90045-5"},{"key":"46_CR10","doi-asserted-by":"publisher","first-page":"104","DOI":"10.1137\/0130013","volume":"30","author":"F.K. Hwang","year":"1976","unstructured":"Hwang, F.K.: On steiner minimal trees with rectilinear distance. SIAM journal on Applied Mathematics\u00a030, 104\u2013114 (1976)","journal-title":"SIAM journal on Applied Mathematics"},{"issue":"2","key":"46_CR11","doi-asserted-by":"publisher","first-page":"177","DOI":"10.1145\/322123.322124","volume":"26","author":"F.K. Hwang","year":"1979","unstructured":"Hwang, F.K.: An O(n log n) algorithm for rectilinear minimal spanning trees. Journal of the ACM\u00a026(2), 177\u2013182 (1979)","journal-title":"Journal of the ACM"},{"key":"46_CR12","doi-asserted-by":"publisher","first-page":"893","DOI":"10.1109\/43.144853","volume":"11","author":"A.B. Kahng","year":"1992","unstructured":"Kahng, A.B., Robins, G.: A new class of iterated Steiner tree heuristics with good performance. IEEE trans. Computer-Aided Design\u00a011, 893\u2013902 (1992)","journal-title":"IEEE trans. Computer-Aided Design"},{"issue":"2","key":"46_CR13","doi-asserted-by":"publisher","first-page":"355","DOI":"10.1137\/S0097539794264585","volume":"25","author":"S. Khuller","year":"1996","unstructured":"Khuller, S., Raghavachari, B., Young, N.: Low degree spanning trees of small weight. SIAM Journal on Computing\u00a025(2), 355\u2013368 (1996)","journal-title":"SIAM Journal on Computing"},{"key":"46_CR14","doi-asserted-by":"publisher","first-page":"48","DOI":"10.1090\/S0002-9939-1956-0078686-7","volume":"7","author":"M. Kruskal","year":"1956","unstructured":"Kruskal, M.: On the shortest spanning subtree of a graph, and the traveling salesman problem. Proc. Amer. Math Soc.\u00a07, 48\u201350 (1956)","journal-title":"Proc. Amer. Math Soc."},{"key":"46_CR15","doi-asserted-by":"publisher","first-page":"200","DOI":"10.1137\/0209017","volume":"9","author":"D.T. Lee","year":"1980","unstructured":"Lee, D.T., Wong, C.K.: Voronoi diagrams in L1(L1) metric with 2-dimensional storage applications. SIAM Journal of Computing\u00a09, 200\u2013211 (1980)","journal-title":"SIAM Journal of Computing"},{"key":"46_CR16","doi-asserted-by":"publisher","first-page":"231","DOI":"10.1016\/0196-6774(84)90029-4","volume":"5","author":"C.H. Papadimitriou","year":"1984","unstructured":"Papadimitriou, C.H., Vazirani, U.V.: On two geometric problems relating to the traveling salesman problem. Journal of Algorithms\u00a05, 231\u2013246 (1984)","journal-title":"Journal of Algorithms"},{"key":"46_CR17","volume-title":"Physical Design Automation of VLSI Systems","author":"B.T. Preas","year":"1988","unstructured":"Preas, B.T., Lorenzetti, M.J.: Physical Design Automation of VLSI Systems. Benjamin\/Cummings, Menlo Park, CA (1988)"},{"key":"46_CR18","doi-asserted-by":"crossref","first-page":"1389","DOI":"10.1002\/j.1538-7305.1957.tb01515.x","volume":"36","author":"A. Prim","year":"1957","unstructured":"Prim, A.: Shortest connecting networks and some generalizations. Bell Syst. Tech. J.\u00a036, 1389\u20131401 (1957)","journal-title":"Bell Syst. Tech. J."},{"key":"46_CR19","doi-asserted-by":"crossref","unstructured":"Ravi, R., J.onemann: A matter of degree: Improved approximation algorithms for degree- bounded MSTs. In: Proc. ACM Symposium on Theory of Computing (2000)","DOI":"10.1145\/335305.335371"},{"key":"46_CR20","doi-asserted-by":"publisher","first-page":"151","DOI":"10.1007\/BF02570700","volume":"14","author":"G. Robins","year":"1995","unstructured":"Robins, G., Salowe, J.S.: Low-degree minimum spanning tree. Discrete and Computational Geometry\u00a014, 151\u2013165 (1995)","journal-title":"Discrete and Computational Geometry"},{"key":"46_CR21","doi-asserted-by":"publisher","first-page":"207","DOI":"10.1007\/BF01759042","volume":"6","author":"G.M. Shute","year":"1991","unstructured":"Shute, G.M., Deneen, L.L., Thomborson, C.D.: An O(n log n) plane-sweep algorithm for L1 and L1 delaunay triangulations. Algorithmica\u00a06, 207\u2013221 (1991)","journal-title":"Algorithmica"},{"issue":"4","key":"46_CR22","doi-asserted-by":"publisher","first-page":"721","DOI":"10.1137\/0211059","volume":"11","author":"A.C.-C. Yao","year":"1982","unstructured":"Yao, A.C.-C.: On constructing minimum spanning trees in k-dimensional spaces and related problems. SIAM Journal on Computing\u00a011(4), 721\u2013736 (1982)","journal-title":"SIAM Journal on Computing"},{"key":"46_CR23","doi-asserted-by":"crossref","unstructured":"Zhou, H., Shenoy, N., Nicholls, W.: Efficient spanning tree construction without delaunay triangulation. Information Processing Letters 81(5) (2002)","DOI":"10.1016\/S0020-0190(01)00232-0"}],"container-title":["Lecture Notes in Computer Science","Integrated Circuit and System Design. Power and Timing Modeling, Optimization and Simulation"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-540-30205-6_46.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,11,18]],"date-time":"2020-11-18T23:48:22Z","timestamp":1605743302000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-540-30205-6_46"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2004]]},"ISBN":["9783540230953","9783540302056"],"references-count":23,"URL":"https:\/\/doi.org\/10.1007\/978-3-540-30205-6_46","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2004]]}}}