{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,4]],"date-time":"2024-09-04T23:59:59Z","timestamp":1725494399706},"publisher-location":"Berlin, Heidelberg","reference-count":26,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540423065"},{"type":"electronic","value":"9783540477389"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2001]]},"DOI":"10.1007\/3-540-47738-1_30","type":"book-chapter","created":{"date-parts":[[2007,11,6]],"date-time":"2007-11-06T22:52:49Z","timestamp":1194389569000},"page":"318-329","source":"Crossref","is-referenced-by-count":1,"title":["3\u2014Dimensional Single Active Layer Routing"],"prefix":"10.1007","author":[{"given":"Andr\u00e1s","family":"Recski","sequence":"first","affiliation":[]},{"given":"D\u00e1vid","family":"Szeszl\u00e9r","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2001,9,20]]},"reference":[{"key":"30_CR1","doi-asserted-by":"publisher","first-page":"241","DOI":"10.1007\/BF01759044","volume":"6","author":"A. Aggarwal","year":"1991","unstructured":"Aggarwal, A., M. Klawe, D. Lichtenstein, N. Linial, and A. Wigderson, 1991. A lower bound on the area of permutation layouts, Algorithmica 6, 241\u2013255.","journal-title":"Algorithmica"},{"key":"30_CR2","doi-asserted-by":"publisher","first-page":"1321","DOI":"10.1137\/S0097539796312733","volume":"29","author":"A. Aggarwal","year":"2000","unstructured":"Aggarwal, A., J. Kleinberg, and D. P. Williamson, 2000. Node-disjoint paths on the mesh and a new trade-off in VLSI layout, SIAM J. Computing 29, 1321\u20131333.","journal-title":"SIAM J. Computing"},{"key":"30_CR3","first-page":"205","volume":"2","author":"S. B. Baker","year":"1984","unstructured":"Baker S. B., S. N. Bhatt, and F. T. Leighton, 1984. An approximation algorithm for Manhattan routing, Advances in Computing Research 2, 205\u2013229.","journal-title":"Advances in Computing Research"},{"key":"30_CR4","doi-asserted-by":"publisher","first-page":"481","DOI":"10.1007\/BF02057159","volume":"58","author":"E. Boros","year":"1995","unstructured":"Boros, E., A. Recski and F. Wettl, 1995. Unconstrained multilayer switchbox routing, Ann. Oper. Res. 58, 481\u2013491.","journal-title":"Ann. Oper. Res."},{"key":"30_CR5","doi-asserted-by":"publisher","first-page":"223","DOI":"10.1109\/TCAD.1983.1270040","volume":"CAD-2","author":"M. Burstein","year":"1983","unstructured":"Burstein, M. and R. Pelavin, 1983. Hierarchical wire routing, IEEE Trans. Computer-Aided Design CAD-2, 223\u2013234.","journal-title":"IEEE Trans. Computer-Aided Design"},{"key":"30_CR6","doi-asserted-by":"publisher","first-page":"21","DOI":"10.1016\/0167-9260(83)90004-4","volume":"1","author":"M. Burstein","year":"1983","unstructured":"Burstein, M. and R. Pelavin, 1983. Hierarchical channel router, Integration, the VLSI Journal 1, 21\u201338.","journal-title":"Integration, the VLSI Journal"},{"key":"30_CR7","first-page":"117","volume-title":"3rd Caltech Conference on VLSI","author":"W. S. Chan","year":"1983","unstructured":"Chan, Wan S., 1983. A new channel routing algorithm, in: R. Bryant, ed. 3rd Caltech Conference on VLSI, Comp. Sci. Press, Rockville, 117\u2013139."},{"key":"30_CR8","doi-asserted-by":"publisher","first-page":"684","DOI":"10.1109\/43.3208","volume":"CAD-7","author":"J.P. Cohoon","year":"1988","unstructured":"Cohoon, J.P. and P. L. Heck, 1988. BEAVER: A computational-geometry-based tool for switchbox routing, IEEE Trans. Computer-Aided Design CAD-7, 684\u2013697.","journal-title":"IEEE Trans. Computer-Aided Design"},{"key":"30_CR9","doi-asserted-by":"publisher","first-page":"253","DOI":"10.1002\/net.3230080308","volume":"8","author":"M. Cutler","year":"1978","unstructured":"Cutler, M. and Y. Shiloach, 1978. Permutation layout, Networks 8, 253\u2013278.","journal-title":"Networks"},{"key":"30_CR10","doi-asserted-by":"crossref","unstructured":"Deutsch, D, 1976. A dogleg channel router, Proc. 13rd Design Automation Conf. 425\u2013433.","DOI":"10.1145\/800146.804843"},{"key":"30_CR11","doi-asserted-by":"crossref","unstructured":"Enbody, R.J., G. Lynn, and K. H. Tan, 1991. Routing the 3-D chip, Proc. 28th ACM\/IEEE Design Automation Conf. 132\u2013137.","DOI":"10.1145\/127601.127644"},{"key":"30_CR12","first-page":"115","volume":"1","author":"T. H. u. r. h. b. a. i. A. HajnalJ. S. Gallai","year":"1958","unstructured":"Gallai T. His unpublished results have been announced in A. Hajnal and J. Sur\u00e1nyi, 1958. \u00dcber die Aufl\u00f6sung von Graphen in vollst\u00e4ndige Teilgraphen, Ann. Univ. Sci. Budapest E\u00f6tv\u00f6s Sect. Math. 1, 115\u2013123.","journal-title":"Ann. Univ. Sci. Budapest E\u00f6tv\u00f6s Sect. Math."},{"key":"30_CR13","doi-asserted-by":"publisher","first-page":"233","DOI":"10.1007\/BF01840445","volume":"1","author":"R. A. Games","year":"1986","unstructured":"Games, R. A., 1986. Optimal book embeddings of the FFT, Benes, and barrel shifter networks, Algorithmica 1, 233\u2013250.","journal-title":"Algorithmica"},{"key":"30_CR14","doi-asserted-by":"publisher","first-page":"791","DOI":"10.1145\/179812.179927","volume":"41","author":"S. Gao","year":"1994","unstructured":"Gao, S. and M. Kaufmann, 1994. Channel routing of multiterminal nets, J. of the ACM 41, 791\u2013818.","journal-title":"J. of the ACM"},{"key":"30_CR15","unstructured":"Gr\u00f6tschel, M., A. Martin, and R. Weismantel, 1993. Routing in grid graphs by cutting planes, in: G. Rinaldi and L. Wolsey, eds. Integer programming and combinatorial optimization, 447\u2013461."},{"key":"30_CR16","doi-asserted-by":"publisher","first-page":"23","DOI":"10.1109\/TCAD.1985.1270095","volume":"CAD-4","author":"S. E. Hambrusch","year":"1985","unstructured":"Hambrusch, S. E., 1985. Channel routing in overlap models, IEEE Trans. Computer-Aided Design of Integrated Circ. Syst. CAD-4, 23\u201330.","journal-title":"IEEE Trans. Computer-Aided Design of Integrated Circ. Syst."},{"key":"30_CR17","doi-asserted-by":"crossref","unstructured":"Hashimoto, A. and J. Stevens, 1971. Wire routing by optimizing channel assignment, Proc. 8th Design Automation Conf. 214\u2013224.","DOI":"10.1145\/800158.805069"},{"key":"30_CR18","doi-asserted-by":"crossref","unstructured":"LaPaugh A. S., 1980. A polynomial time algorithm for optimal routing around a rectangle, Proc. 21st FOCS Symp. 282\u2013293.","DOI":"10.1109\/SFCS.1980.7"},{"key":"30_CR19","volume-title":"Complexity issues in VLSI: Optimal layouts for the shuffle-exchange graph and other networks","author":"T. Leighton","year":"1983","unstructured":"Leighton, T., 1983. Complexity issues in VLSI: Optimal layouts for the shuffle-exchange graph and other networks, The MIT Press, Cambridge, MA."},{"key":"30_CR20","doi-asserted-by":"publisher","first-page":"793","DOI":"10.1137\/0215057","volume":"15","author":"T. Leighton","year":"1986","unstructured":"Leighton, T. and A. L. Rosenberg, 1986. Three-dimensional circuit layouts, SIAM J. Computing 15, 793\u2013813.","journal-title":"SIAM J. Computing"},{"key":"30_CR21","first-page":"643","volume-title":"Proc. Tenth Annual ACMSIAM Symp. on Discrete Algorithms","author":"T. Leighton","year":"1999","unstructured":"Leighton, T., S. Rao and A. Srinivasan, 1999. New algorithmic aspects of the Local Lemma with applications to routing and partitioning, Proc. Tenth Annual ACMSIAM Symp. on Discrete Algorithms, ACM\/SIAM, New York and Philadelphia, 643\u2013652."},{"key":"30_CR22","doi-asserted-by":"publisher","first-page":"129","DOI":"10.1016\/0167-9260(85)90029-X","volume":"3","author":"W.K. Luk","year":"1985","unstructured":"Luk, W.K., 1985. A greedy switch-box router, Integration, the VLSI Journal 3, 129\u2013149.","journal-title":"Integration, the VLSI Journal"},{"key":"30_CR23","doi-asserted-by":"publisher","first-page":"397","DOI":"10.1145\/2402.322384","volume":"30","author":"A.L. Rosenberg","year":"1983","unstructured":"Rosenberg, A.L., 1983. Three-dimensional VLSI: A case study, J. ACM. 30, 397\u2013416.","journal-title":"J. ACM."},{"key":"30_CR24","doi-asserted-by":"publisher","first-page":"179","DOI":"10.1002\/net.3230100208","volume":"10","author":"I. Shirakawa","year":"1980","unstructured":"Shirakawa, I., 1980. Some comments on permutation layout, Networks 10, 179\u2013182.","journal-title":"Networks"},{"key":"30_CR25","first-page":"155","volume":"40","author":"D. Szeszl\u00e9r","year":"1997","unstructured":"Szeszl\u00e9r D., 1997. Switchbox routing in the multilayer Manhattan model, Ann. Univ. Sci. Budapest E\u00f6tv\u00f6s Sect. Math, 40, 155\u2013164.","journal-title":"Ann. Univ. Sci. Budapest E\u00f6tv\u00f6s Sect. Math"},{"key":"30_CR26","doi-asserted-by":"publisher","first-page":"31","DOI":"10.1109\/TCAD.1985.1270096","volume":"CAD-4","author":"T. G. Szymanski","year":"1985","unstructured":"Szymanski, T. G., 1985. Dogleg channel routing is NP-complete, IEEE Trans. Computer-Aided Design of Integrated Circ. Syst. CAD-4, 31\u201341.","journal-title":"IEEE Trans. Computer-Aided Design of Integrated Circ. Syst."}],"container-title":["Lecture Notes in Computer Science","Discrete and Computational Geometry"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-47738-1_30","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,4]],"date-time":"2019-05-04T06:19:27Z","timestamp":1556950767000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-47738-1_30"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2001]]},"ISBN":["9783540423065","9783540477389"],"references-count":26,"URL":"https:\/\/doi.org\/10.1007\/3-540-47738-1_30","relation":{},"ISSN":["0302-9743"],"issn-type":[{"type":"print","value":"0302-9743"}],"subject":[],"published":{"date-parts":[[2001]]}}}