{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,4]],"date-time":"2024-09-04T13:08:04Z","timestamp":1725455284546},"publisher-location":"Berlin, Heidelberg","reference-count":10,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540605737"},{"type":"electronic","value":"9783540477662"}],"license":[{"start":{"date-parts":[[1995,1,1]],"date-time":"1995-01-01T00:00:00Z","timestamp":788918400000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1995]]},"DOI":"10.1007\/bfb0015438","type":"book-chapter","created":{"date-parts":[[2005,11,13]],"date-time":"2005-11-13T06:50:06Z","timestamp":1131864606000},"page":"322-331","update-policy":"http:\/\/dx.doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":3,"title":["A fast algorithm for computing optimal rectilinear Steiner trees for extremal point sets"],"prefix":"10.1007","author":[{"given":"Siu-Wing","family":"Cheng","sequence":"first","affiliation":[]},{"given":"Chi-Keung","family":"Tang","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2005,6,9]]},"reference":[{"key":"37_CR1","doi-asserted-by":"crossref","first-page":"109","DOI":"10.1002\/net.3230200110","volume":"7","author":"M. Bern","year":"1990","unstructured":"M. Bern, Faster Exact Algorithms for Steiner Tree in Planar Networks, Networks, 7 (1990), pp. 109\u2013120.","journal-title":"Networks"},{"key":"37_CR2","first-page":"523","volume":"762","author":"S.W. Cheng","year":"1993","unstructured":"S.W. Cheng, A. Lim, and C. Wu, Optimal Rectilinear Steiner Tree for Extremal Point Sets, in Proc. Int'l Symp. Alg. and Comput. (ISAAC), 1993, LNCS 762, pp. 523\u2013532.","journal-title":"LNCS"},{"key":"37_CR3","unstructured":"S.W. Cheng and C.K. Tang, A Fast Algorithm for Computing Optimal Rectilinear Steiner Trees for Extremal Point Sets, Technical Report HKUST-CS95-20, Department of Computer Science, HKUST."},{"key":"37_CR4","doi-asserted-by":"crossref","first-page":"634","DOI":"10.1287\/moor.12.4.634","volume":"12","author":"R. E. Erickson","year":"1987","unstructured":"R. E. Erickson, C. Monma, and A. F. Veinott, Send-and-split Method for Minimum-cost Network Flows, Mathematical Operation Research, 12 (1987), pp. 634\u2013664.","journal-title":"Mathematical Operation Research"},{"key":"37_CR5","first-page":"351","volume":"834","author":"M. Kaufmann","year":"1994","unstructured":"M. Kaufmann, S. Gao, and K. Thulasiraman, On Steiner Minimal Trees in Grid Graphs and Its Application to VLSI Routing, in Proc. Int'l Symp. Alg. and Comput. (ISAAC), 1994, LNCS 834, pp. 351\u2013359.","journal-title":"LNCS"},{"key":"37_CR6","doi-asserted-by":"crossref","unstructured":"C.E. Leiserson and F.M. Maley, Algorithms for Routing and Testing Routability of Planar VLSI Layouts, Proc. 7th Ann. Symp. Theory of Comput., 1985, pp. 69\u201378.","DOI":"10.1145\/22145.22153"},{"key":"37_CR7","doi-asserted-by":"crossref","first-page":"55","DOI":"10.1002\/net.3230180108","volume":"18","author":"J. Provan","year":"1988","unstructured":"J. Provan, Convexity and the Steiner Tree Problem, Networks, 18 (1988), pp. 55\u201372.","journal-title":"Networks"},{"key":"37_CR8","doi-asserted-by":"crossref","first-page":"247","DOI":"10.1007\/BF01758761","volume":"7","author":"D. Richards","year":"1992","unstructured":"D. Richards and J. Salowe, A Linear-Time Algorithm to Construct a Rectilinear Steiner Minimal Tree for k-Extremal Point Sets, Algorithmica, 7 (1992), pp. 247\u2013276.","journal-title":"Algorithmica"},{"key":"37_CR9","unstructured":"J.D. Ullamn, Computational Aspects of VLSI, Computer Science Press, 1984."},{"key":"37_CR10","unstructured":"Y. Y. Yang and O. Wing. Optimal and Suboptimal Solution Algorithms for the Wiring Problem. Proc. IEEE Int'l Symp. Circuit Theory, pp. 154\u2013158, 1972."}],"container-title":["Lecture Notes in Computer Science","Algorithms and Computations"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BFb0015438","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,1,9]],"date-time":"2020-01-09T04:22:43Z","timestamp":1578543763000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/BFb0015438"}},"subtitle":["Extended abstract"],"short-title":[],"issued":{"date-parts":[[1995]]},"ISBN":["9783540605737","9783540477662"],"references-count":10,"URL":"https:\/\/doi.org\/10.1007\/bfb0015438","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[1995]]},"assertion":[{"value":"9 June 2005","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}}]}}