{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,9,28]],"date-time":"2025-09-28T12:44:58Z","timestamp":1759063498178},"reference-count":20,"publisher":"Springer Science and Business Media LLC","issue":"1-6","license":[{"start":{"date-parts":[[1991,6,1]],"date-time":"1991-06-01T00:00:00Z","timestamp":675734400000},"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":[[1991,6]]},"DOI":"10.1007\/bf01759036","type":"journal-article","created":{"date-parts":[[2005,6,16]],"date-time":"2005-06-16T10:43:56Z","timestamp":1118918636000},"page":"83-101","source":"Crossref","is-referenced-by-count":4,"title":["Optimal multilayer channel routing with overlap"],"prefix":"10.1007","volume":"6","author":[{"given":"Martin L.","family":"Brady","sequence":"first","affiliation":[]},{"given":"Donna J.","family":"Brown","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"BF01759036_CR1","doi-asserted-by":"crossref","unstructured":"Berger, B., M. Brady, D. J. Brown, and T. Leighton, Nearly Optimal Algorithms and Bounds for Multilayer Channel Routing,Journal of the Association for Computing Machinery, to appear.","DOI":"10.1145\/201019.201037"},{"key":"BF01759036_CR2","unstructured":"Bolognesi, T., and D. J. Brown, A Channel Routing Algorithm with Bounded Wire Length, unpublished manuscript, Coordinated Science Laboratory, University of Illinois at Urbana-Champaign (1982)."},{"key":"BF01759036_CR3","first-page":"245","volume-title":"Advances in Computing Research","author":"M. Brady","year":"1984","unstructured":"Brady, M., and D. J. Brown, VLSI Routing: Four Layers Suffice,Advances in Computing Research, Vol. 2, ed. F. P. Preparata, JAI Press, Greenwich, CT, pp. 245\u2013257 (1984)."},{"key":"BF01759036_CR4","unstructured":"Brady, M., and D. J. Brown, An Algorithm for Three Layer Channel Routing Using Unrestricted Overlap,Proc. 23rd Allerton Conf. on Communication, Control, and Computing, pp. 674\u2013675 (Oct. 1985)."},{"key":"BF01759036_CR5","unstructured":"Brady, M., and D. J. Brown, Optimal Multilayer Channel Routing with Overlap,Proc. 4th MIT Conf. on Advanced Research in VLSI, pp. 281\u2013296 (Apr. 1985)."},{"key":"BF01759036_CR6","unstructured":"Brown, D. J., A 7\/4d Algorithm for Two Layer Routing with Overlap, draft (1983)."},{"issue":"2","key":"BF01759036_CR7","doi-asserted-by":"crossref","first-page":"156","DOI":"10.1109\/TCAD.1984.1270070","volume":"3","author":"Y. K. Chen","year":"1984","unstructured":"Chen, Y. K., and M. L. Liu, Three Layer Channel Routing,IEEE Trans, on Computer-Aided Design of Integrated Circuits and Systems,3 (2), 156\u2013163 (Apr, 1984).","journal-title":"IEEE Trans, on Computer-Aided Design of Integrated Circuits and Systems"},{"key":"BF01759036_CR8","doi-asserted-by":"crossref","unstructured":"Deutsch, D. N., A Dogleg Channel Router,Proc. 13th Design Automation Conf., pp. 425\u2013433 (June 1976).","DOI":"10.1145\/800146.804843"},{"key":"BF01759036_CR9","doi-asserted-by":"crossref","unstructured":"Gao, S., An Algorithm for Two-Layer Channel Routing,Proc. 2nd Annual Symp. on Theoretical Aspects in Computer Science, pp. 151\u2013160 (1985).","DOI":"10.1007\/BFb0024004"},{"issue":"2","key":"BF01759036_CR10","doi-asserted-by":"crossref","first-page":"223","DOI":"10.1007\/BF01840444","volume":"1","author":"S. Gao","year":"1986","unstructured":"Gao, S., and S. Hambrusch, Two-Layer Channel Routing with Vertical Unit-Length Overlap,Algorithmica,1 (2), 223\u2013232 (1986).","journal-title":"Algorithmica"},{"key":"BF01759036_CR11","doi-asserted-by":"crossref","unstructured":"Gao, S., and M. Kaufmann, Channel Routing of Multiterminal Nets,Proc. 28thIEEE Symp. on Foundations of Computer Science, pp. 316\u2013325 (Oct. 1987). (Submitted toJournal of the Association for Computing Machinery.)","DOI":"10.1109\/SFCS.1987.13"},{"key":"BF01759036_CR12","unstructured":"Hambrusch, S., Using Overlap and Minimizing Contact Points in Channel Routing,Proc. 21stAllerton Conf. on Communication, Control, and Computing, pp. 256\u2013257 (Oct. 1983)."},{"issue":"1","key":"BF01759036_CR13","doi-asserted-by":"crossref","first-page":"23","DOI":"10.1109\/TCAD.1985.1270095","volume":"4","author":"S. Hambrusch","year":"1985","unstructured":"Hambrusch, S., Channel Routing Algorithms for Overlap Models,IEEE Trans, on Computer-Aided Design of Integrated Circuits and Systems,4 (1), 23\u201330 (Jan. 1985).","journal-title":"IEEE Trans, on Computer-Aided Design of Integrated Circuits and Systems"},{"key":"BF01759036_CR14","unstructured":"Leighton, F. T., New Lower Bounds for Channel Routing, MIT VLSI Memo 82-71 (Jan. 1982). (Submitted toSIAM Journal on Discrete Mathematics)."},{"key":"BF01759036_CR15","doi-asserted-by":"crossref","first-page":"427","DOI":"10.1109\/TC.1984.1676459","volume":"33","author":"F. P. Preparata","year":"1984","unstructured":"Preparata, F. P., and W. Lipski, Jr., Optimal Three-Layer Channel Routing,IEEE Trans, on Computers,33, 427\u2013437 (May 1984).","journal-title":"IEEE Trans, on Computers"},{"key":"BF01759036_CR16","doi-asserted-by":"crossref","unstructured":"Rivest, R. L., A. Baratz, and G. Miller, Provably Good Channel Routing Algorithms,Proc. 1981 CMU Conf. on VLSI Systems and Computations, pp. 153\u2013159 (Oct. 1981).","DOI":"10.1007\/978-3-642-68402-9_18"},{"key":"BF01759036_CR17","doi-asserted-by":"crossref","unstructured":"Rivest, R. L., and C. M. Fiduccia, A Greedy Channel Router,Proc. 19th Design Automation Conf., pp. 418\u2013424 (June 1982).","DOI":"10.1109\/DAC.1982.1585533"},{"issue":"3","key":"BF01759036_CR18","doi-asserted-by":"crossref","first-page":"397","DOI":"10.1145\/2402.322384","volume":"30","author":"A. Rosenberg","year":"1983","unstructured":"Rosenberg, A., Three Dimensional VLSI: A Case Study,Journal of the Association for Computing Machinery,30 (3), 397\u2013416 (July 1983).","journal-title":"Journal of the Association for Computing Machinery"},{"key":"BF01759036_CR19","first-page":"255","volume":"25","author":"M. Sarrafzadeh","year":"1985","unstructured":"Sarrafzadeh, M., and F. P. Preparata, Compact Channel Routing of Multiterminal Nets,Annals of Discrete Mathematics,25, 255\u2013280 (1985).","journal-title":"Annals of Discrete Mathematics"},{"issue":"1","key":"BF01759036_CR20","doi-asserted-by":"crossref","first-page":"25","DOI":"10.1109\/TCAD.1982.1269993","volume":"1","author":"T. Yoshimura","year":"1982","unstructured":"Yoshimura, T., and E. S. Kuh, Efficient Algorithms for Channel Routing,IEEE Trans, on Computer-Aided Design of Integrated Circuits and Systems,1 (1), 25\u201335 (Jan. 1982).","journal-title":"IEEE Trans, on Computer-Aided Design of Integrated Circuits and Systems"}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF01759036.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/BF01759036\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF01759036","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,4,7]],"date-time":"2020-04-07T19:27:12Z","timestamp":1586287632000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/BF01759036"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1991,6]]},"references-count":20,"journal-issue":{"issue":"1-6","published-print":{"date-parts":[[1991,6]]}},"alternative-id":["BF01759036"],"URL":"https:\/\/doi.org\/10.1007\/bf01759036","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[1991,6]]}}}