{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,9,28]],"date-time":"2025-09-28T12:49:26Z","timestamp":1759063766241},"reference-count":16,"publisher":"Springer Science and Business Media LLC","issue":"1-4","license":[{"start":{"date-parts":[[1986,11,1]],"date-time":"1986-11-01T00:00:00Z","timestamp":531187200000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[1986,11]]},"DOI":"10.1007\/bf01840444","type":"journal-article","created":{"date-parts":[[2005,7,13]],"date-time":"2005-07-13T21:29:13Z","timestamp":1121290153000},"page":"223-232","source":"Crossref","is-referenced-by-count":11,"title":["Two-layer channel routing with vertical unit-length overlap"],"prefix":"10.1007","volume":"1","author":[{"given":"Shaodi","family":"Gao","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Susanne","family":"Hambrusch","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"BF01840444_CR1","unstructured":"B. Berger, M. Brady, D. Brown, and F. T. Leighton. Personal communication."},{"key":"BF01840444_CR2","doi-asserted-by":"crossref","unstructured":"B. S. Baker, S. N. Bhatt, and F. T. Leighton. \u2018An Approximation Algorithm for Manhatten Routing\u2019.Proceedings of the 15th Ann. ACM Syrnp. on Theory of Computing, 1983, pp. 477\u2013486.","DOI":"10.1145\/800061.808779"},{"key":"BF01840444_CR3","doi-asserted-by":"crossref","unstructured":"D. J. Brown and R. L. Rivest. \u2018New Lower Bounds for Channel Width\u2019.Proceedings of the CMU Conf. on VLSI Systems and Comput., 1981, pp. 153\u2013159.","DOI":"10.1007\/978-3-642-68402-9_20"},{"key":"BF01840444_CR4","doi-asserted-by":"crossref","unstructured":"D. N. Deutsch. \u2018A Dogleg Channel Router\u2019.Proceedings of the 13th IEEE Design Automation Conf., 1976, pp. 425\u2013433.","DOI":"10.1145\/800146.804843"},{"key":"BF01840444_CR5","doi-asserted-by":"crossref","unstructured":"S. Gao. \u2018An Algorithm for Two-layer Channel Routing\u2019.Proceedings of 2nd Ann. Symp. on Theoretical Aspects in Computer Sci., 1985, pp. 151\u2013160.","DOI":"10.1007\/BFb0024004"},{"key":"BF01840444_CR6","doi-asserted-by":"crossref","unstructured":"S. E. Hambrusch. \u2018Channel Routing Algorithms for Overlap Models\u2019.IEEE Trans. CAD, Vol. cad-4, Jan. 1985, pp. 23\u201331.","DOI":"10.1109\/TCAD.1985.1270095"},{"key":"BF01840444_CR7","doi-asserted-by":"crossref","unstructured":"A. Hashimoto and J. Stevens. \u2018Wire Routing by Optimizing Channel Assignment within Large Apertures\u2019,Proceedings of the 8th Design Aut. Conf., 1971, pp. 155\u2013169.","DOI":"10.1145\/800158.805069"},{"key":"BF01840444_CR8","first-page":"328","volume-title":"Lecture Notes in Computer Science","author":"M. Kaufmann","year":"1985","unstructured":"M. Kaufmann and K. Mehlhorn. \u2018Routing Through a Generalized Switchbox\u2019.Lecture Notes in Computer Science, No. 194 (ICALP 85), Springer-Verlag, New York, 1985, pp. 328\u2013333."},{"key":"BF01840444_CR9","unstructured":"F. T. Leighton. \u2018New Lower Bounds for Channel Routing\u2019. Unpublished manuscript, 1981."},{"issue":"1","key":"BF01840444_CR10","doi-asserted-by":"crossref","first-page":"60","DOI":"10.1145\/4904.4994","volume":"33","author":"K. Mehlhorn","year":"1986","unstructured":"K. Mehlhorn and F. P. Prepatara. \u2018Routing Through a Rectangle\u2019,J. ACM,33, 1 (1986), 60\u201385.","journal-title":"J. ACM"},{"key":"BF01840444_CR11","doi-asserted-by":"crossref","unstructured":"F. P. Preparata and W. Lipski. \u2018Three Layers are Enough\u2019.Proceedings of the 23rd Ann. IEEE Foundations of Comput. Sci. Conf., 1982, pp. 350\u2013357.","DOI":"10.1109\/SFCS.1982.47"},{"key":"BF01840444_CR12","doi-asserted-by":"crossref","unstructured":"R. L. Rivest. \u2018The Pi-Placement and Interconnect-System\u2019,Proceedings of the 19th Design Automation Conf., 1982, pp. 475\u2013481.","DOI":"10.1109\/DAC.1982.1585541"},{"key":"BF01840444_CR13","doi-asserted-by":"crossref","unstructured":"R. L. Rivest, A. E. Baratz, and G. Miller, \u2018Provably Good Channel Routing Algorithms\u2019,Proceedings of the CMU Conf. on VLSI Systems and Comput., 1981, pp. 153\u2013159.","DOI":"10.1007\/978-3-642-68402-9_18"},{"key":"BF01840444_CR14","doi-asserted-by":"crossref","unstructured":"R. L. Rivest and C. M. Fiduccia, \u2018A \u201cGreedy\u2019 Channel Router\u2019,Proceedings of the 19th IEEE Design Automation Conf., 1982, pp. 418\u2013424.","DOI":"10.1109\/DAC.1982.1585533"},{"key":"BF01840444_CR15","unstructured":"M. Sarrafzadeh and F. P. Prepatara. \u2018Compact Channel Routing of Multiterminal Nets\u2019. To appear inAnn. Discrete Maths."},{"key":"BF01840444_CR16","doi-asserted-by":"crossref","unstructured":"T. Yoshimura and E. S. Kuh. \u2018Efficient Algorithms for Channel Routing\u2019.IEEE Trans. CAD, 1982, pp. 25\u201335.","DOI":"10.1109\/TCAD.1982.1269993"}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF01840444.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/BF01840444\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF01840444","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,4,8]],"date-time":"2020-04-08T06:58:52Z","timestamp":1586329132000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/BF01840444"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1986,11]]},"references-count":16,"journal-issue":{"issue":"1-4","published-print":{"date-parts":[[1986,11]]}},"alternative-id":["BF01840444"],"URL":"https:\/\/doi.org\/10.1007\/bf01840444","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[1986,11]]}}}