{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,25]],"date-time":"2025-03-25T14:28:05Z","timestamp":1742912885470,"version":"3.40.3"},"publisher-location":"New York, NY","reference-count":17,"publisher":"Springer New York","isbn-type":[{"type":"print","value":"9781493928637"},{"type":"electronic","value":"9781493928644"}],"license":[{"start":{"date-parts":[[2016,1,1]],"date-time":"2016-01-01T00:00:00Z","timestamp":1451606400000},"content-version":"unspecified","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":[[2016]]},"DOI":"10.1007\/978-1-4939-2864-4_337","type":"book-chapter","created":{"date-parts":[[2016,4,21]],"date-time":"2016-04-21T20:03:30Z","timestamp":1461269010000},"page":"1792-1797","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Rectilinear Steiner Tree"],"prefix":"10.1007","author":[{"given":"Hai","family":"Zhou","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2016,4,22]]},"reference":[{"key":"320_CR18211","doi-asserted-by":"publisher","first-page":"753","DOI":"10.1145\/290179.290180","volume":"45","author":"S Arora","year":"1998","unstructured":"Arora S (1998) Polynomial-time approximation schemes for Euclidean TSP and other geometric problem. J ACM 45:753\u2013782","journal-title":"J ACM"},{"key":"320_CR18212","doi-asserted-by":"publisher","first-page":"1563","DOI":"10.1109\/43.331412","volume":"13","author":"M Borah","year":"1994","unstructured":"Borah M, Owens RM, Irwin MJ (1994) An edge-based heuristic for steiner routing. IEEE Trans Comput Aided Des 13:1563\u20131568","journal-title":"IEEE Trans Comput Aided Des"},{"key":"320_CR18213","first-page":"696","volume-title":"FLUTE: Fast lookup table based wirelength estimation technique","author":"C Chu","year":"2004","unstructured":"Chu C (2004) FLUTE: Fast lookup table based wirelength estimation technique. In: Proceedings of the international conference on computer-aided design, San Jose, pp\u00a0696\u2013701"},{"key":"320_CR18214","first-page":"28","volume-title":"Fast and accurate rectilinear steiner minimal tree algorithm for VLSI design","author":"C Chu","year":"2005","unstructured":"Chu C, Wong YC (2005) Fast and accurate rectilinear steiner minimal tree algorithm for VLSI design. In: Proceedings of the international symposium on physical design, San Francisco, pp\u00a028\u201335"},{"key":"320_CR18215","volume-title":"Introduction to algorithms","author":"TH Cormen","year":"1989","unstructured":"Cormen TH, Leiserson CE, Rivest RL (1989) Introduction to algorithms. MIT, Cambridge"},{"key":"320_CR18216","doi-asserted-by":"publisher","first-page":"1351","DOI":"10.1109\/43.329264","volume":"13","author":"J Griffith","year":"1994","unstructured":"Griffith J, Robins G, Salowe JS, Zhang T (1994) Closing the gap: near-optimal steiner trees in polynomial time. IEEE Trans Comput Aided Des 13:1351\u20131365","journal-title":"IEEE Trans Comput Aided Des"},{"key":"320_CR18217","doi-asserted-by":"publisher","first-page":"185","DOI":"10.1109\/43.46785","volume":"9","author":"JM Ho","year":"1990","unstructured":"Ho JM, Vijayan G, Wong CK (1990) New algorithms for the rectilinear steiner tree problem. IEEE Trans Comput Aided Des 9:185\u2013193","journal-title":"IEEE Trans Comput Aided Des"},{"key":"320_CR18218","doi-asserted-by":"publisher","first-page":"104","DOI":"10.1137\/0130013","volume":"30","author":"FK Hwang","year":"1976","unstructured":"Hwang FK (1976) On steiner minimal trees with rectilinear distance. SIAM J Appl Math 30:104\u2013114","journal-title":"SIAM J Appl Math"},{"key":"320_CR18219","first-page":"827","volume-title":"Highly scalable algorithms for rectilinear and octilinear steiner trees","author":"AB Kahng","year":"2003","unstructured":"Kahng AB, Mandoiu II, Zelikovsky A (2003) Highly scalable algorithms for rectilinear and octilinear steiner trees. In: Proceedings of the Asia and South Pacific design automation conference, Kitakyushu, pp\u00a0827\u2013833"},{"key":"320_CR18220","doi-asserted-by":"publisher","first-page":"893","DOI":"10.1109\/43.144853","volume":"11","author":"AB Kahng","year":"1992","unstructured":"Kahng AB, Robins G (1992) A new class of iterative steiner tree heuristics with good performance. IEEE Trans Comput Aided Des 11:893\u2013902","journal-title":"IEEE Trans Comput Aided Des"},{"key":"320_CR18221","doi-asserted-by":"publisher","DOI":"10.1109\/ICCAD.1999.810641","volume-title":"A new heuristic for rectilinear steiner trees","author":"II Mandoiu","year":"1999","unstructured":"Mandoiu II, Vazirani VV, Ganley JL (1999) A new heuristic for rectilinear steiner trees. In: Proceedings of the international conference on computer-aided design, San Jose"},{"key":"320_CR18222","unstructured":"Rajagopalan S, Vazirani VV (1999) On the bidirected cut relaxation for the metric steiner tree problem. In: Proceedings of the 10th ACM-SIAM symposium on discrete algorithms, Baltimore, pp\u00a0742\u2013751"},{"key":"320_CR18223","unstructured":"Rohe A (2001) Sequential and parallel algorithms for local routing. Ph.D. thesis, Bonn University, Bonn"},{"key":"320_CR18224","unstructured":"Warme DM, Winter P, Zacharisen M (2003) GeoSteiner 3.1 package. ftp:\/\/ftp.diku.dk\/diku\/users\/martinz\/geosteiner-3.1.tar.gz. Accessed Oct 2003"},{"key":"320_CR18225","unstructured":"Warme DM, Winter P, Zacharisen M (1998) Exact algorithms for plane steiner tree problems: a computational study. Tech. Rep. DIKU-TR-98\/11, Dept. of Computer Science, University of Copenhagen"},{"key":"320_CR18226","doi-asserted-by":"publisher","DOI":"10.1145\/640000.640034","volume-title":"Efficient Steiner tree construction based on spanning graphs","author":"H Zhou","year":"2003","unstructured":"Zhou H (2003) Efficient Steiner tree construction based on spanning graphs. In: ACM international symposium on physical design, Monterey"},{"key":"320_CR18227","doi-asserted-by":"publisher","first-page":"271","DOI":"10.1016\/S0020-0190(01)00232-0","volume":"81","author":"H Zhou","year":"2002","unstructured":"Zhou H, Shenoy N, Nicholls W (2002) Efficient spanning tree construction without delaunay triangulation. Inf Process Lett 81:271\u2013276","journal-title":"Inf Process Lett"}],"container-title":["Encyclopedia of Algorithms"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-1-4939-2864-4_337","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,3,20]],"date-time":"2019-03-20T17:25:44Z","timestamp":1553102744000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-1-4939-2864-4_337"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016]]},"ISBN":["9781493928637","9781493928644"],"references-count":17,"URL":"https:\/\/doi.org\/10.1007\/978-1-4939-2864-4_337","relation":{},"subject":[],"published":{"date-parts":[[2016]]},"assertion":[{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}}]}}