{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,7]],"date-time":"2025-10-07T14:38:37Z","timestamp":1759847917993,"version":"3.44.0"},"reference-count":50,"publisher":"Elsevier BV","issue":"1-3","license":[{"start":{"date-parts":[[2001,11,1]],"date-time":"2001-11-01T00:00:00Z","timestamp":1004572800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.elsevier.com\/tdm\/userlicense\/1.0\/"},{"start":{"date-parts":[[2001,11,1]],"date-time":"2001-11-01T00:00:00Z","timestamp":1004572800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.elsevier.com\/legal\/tdmrep-license"},{"start":{"date-parts":[[2013,7,17]],"date-time":"2013-07-17T00:00:00Z","timestamp":1374019200000},"content-version":"vor","delay-in-days":4276,"URL":"http:\/\/www.elsevier.com\/open-access\/userlicense\/1.0\/"}],"content-domain":{"domain":["elsevier.com","sciencedirect.com"],"crossmark-restriction":true},"short-container-title":["Discrete Applied Mathematics"],"published-print":{"date-parts":[[2001,11]]},"DOI":"10.1016\/s0166-218x(01)00225-6","type":"journal-article","created":{"date-parts":[[2002,7,25]],"date-time":"2002-07-25T06:01:51Z","timestamp":1027576911000},"page":"199-208","update-policy":"https:\/\/doi.org\/10.1016\/elsevier_cm_policy","source":"Crossref","is-referenced-by-count":2,"title":["Some polynomially solvable subcases of the detailed routing problem in VLSI design"],"prefix":"10.1016","volume":"115","author":[{"given":"Andr\u00e1s","family":"Recski","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"78","reference":[{"key":"10.1016\/S0166-218X(01)00225-6_BIB1","doi-asserted-by":"crossref","unstructured":"S.B. Baker, S.N. Bhatt, F.T. Leighton, An approximation algorithm for Manhattan routing, Proceedings of 15th STOC Symposium, 1983, pp. 477\u2013486.","DOI":"10.1145\/800061.808779"},{"key":"10.1016\/S0166-218X(01)00225-6_BIB2","doi-asserted-by":"crossref","first-page":"500","DOI":"10.1145\/201019.201037","volume":"42","author":"Berger","year":"1995","journal-title":"J. Association for Computing Machinery"},{"key":"10.1016\/S0166-218X(01)00225-6_BIB3","doi-asserted-by":"crossref","first-page":"481","DOI":"10.1007\/BF02057159","article-title":"Unconstrained multilayer switchbox routing","volume":"58","author":"Boros","year":"1995","journal-title":"Ann. Oper. Res."},{"key":"10.1016\/S0166-218X(01)00225-6_BIB4","first-page":"403","article-title":"Polynomial time Manhattan routing without doglegs\u2014a generalization of Gallai's algorithm","volume":"18","author":"Boros","year":"1999","journal-title":"Comput. Artif. Intell."},{"key":"10.1016\/S0166-218X(01)00225-6_BIB5","series-title":"Advances in Computing Research","first-page":"245","article-title":"VLSI routing: four layers suffice","volume":"Vol. 2","author":"Brady","year":"1984"},{"key":"10.1016\/S0166-218X(01)00225-6_BIB6","series-title":"Advanced Research in VLSI","first-page":"281","article-title":"Optimal multilayer channel routing with overlap","author":"Brady","year":"1986"},{"key":"10.1016\/S0166-218X(01)00225-6_BIB7","doi-asserted-by":"crossref","first-page":"83","DOI":"10.1007\/BF01759036","article-title":"Optimal multilayer channel routing with overlap","volume":"6","author":"Brady","year":"1991","journal-title":"Algorithmica"},{"key":"10.1016\/S0166-218X(01)00225-6_BIB8","series-title":"3rd Caltech Conference on VLSI","first-page":"117","article-title":"A new channel routing algorithm","author":"Chan","year":"1983"},{"key":"10.1016\/S0166-218X(01)00225-6_BIB9","unstructured":"H. Chen, E.S. Kuh, A variable-width gridless channel router, ICCAD-85, IEEE International Conference on Computer-Aided Design 1985, pp. 304\u2013306."},{"key":"10.1016\/S0166-218X(01)00225-6_BIB10","doi-asserted-by":"crossref","first-page":"459","DOI":"10.1109\/TCAD.1986.1270217","article-title":"Glitter: a gridless variable-width channel router","volume":"CAD-5","author":"Chen","year":"1986","journal-title":"IEEE Trans. Comput. Aided Design Integrat. Circuit Systems"},{"key":"10.1016\/S0166-218X(01)00225-6_BIB11","doi-asserted-by":"crossref","first-page":"156","DOI":"10.1109\/TCAD.1984.1270070","article-title":"Three-layer channel routing","volume":"CAD-3","author":"Chen","year":"1984","journal-title":"IEEE Trans. Comput. Aided Design Integrat. Circuit Systems"},{"key":"10.1016\/S0166-218X(01)00225-6_BIB12","unstructured":"J. Cong, D.F. Wong, C.L. Liu, A new approach to the three layer channel routing problem, ICCAD-87, IEEE International Conference on Computer-Aided Design, 1987, pp. 378\u2013381."},{"key":"10.1016\/S0166-218X(01)00225-6_BIB13","doi-asserted-by":"crossref","first-page":"217","DOI":"10.1002\/nav.3800010309","article-title":"Minimizing the number of tankers to meet a fixed schedule","volume":"1","author":"Dantzig","year":"1954","journal-title":"Naval Res. Logist. Quart."},{"key":"10.1016\/S0166-218X(01)00225-6_BIB14","doi-asserted-by":"crossref","unstructured":"R.J. Enbody, H.C. Du, Near-optimal n-layer channel routing, Proceedings of the 23rd ACM-IEEE Design Automation Conference, 1986, pp. 708\u2013714.","DOI":"10.1109\/DAC.1986.1586168"},{"key":"10.1016\/S0166-218X(01)00225-6_BIB15","doi-asserted-by":"crossref","first-page":"361","DOI":"10.1007\/BF02579432","article-title":"Disjoint paths in a rectilinear grid","volume":"2","author":"Frank","year":"1982","journal-title":"Combinatorica"},{"key":"10.1016\/S0166-218X(01)00225-6_BIB16","unstructured":"T. Gallai, His unpublished results have been announced in A. Hajnal, J. Sur\u00e1nyi (Eds.), \u00dcber die Aufl\u00f6sung von Graphen in vollst\u00e4ndige Teilgraphen, Ann. Univ. Sci. Budapest E\u00f6tv\u00f6s Sect. Math. 1 (1958) 115\u2013123."},{"key":"10.1016\/S0166-218X(01)00225-6_BIB17","doi-asserted-by":"crossref","first-page":"223","DOI":"10.1007\/BF01840444","article-title":"Two-layer channel routing with vertical unit-length overlap","volume":"1","author":"Gao","year":"1986","journal-title":"Algorithmica"},{"key":"10.1016\/S0166-218X(01)00225-6_BIB18","doi-asserted-by":"crossref","unstructured":"S. Gao, M. Kaufmann, Channel routing of multiterminal nets, Proceeding of the 28th FOCS Symposium, 1987, pp. 316\u2013325.","DOI":"10.1109\/SFCS.1987.13"},{"key":"10.1016\/S0166-218X(01)00225-6_BIB19","doi-asserted-by":"crossref","first-page":"791","DOI":"10.1145\/179812.179927","article-title":"Channel routing of multiterminal nets","volume":"41","author":"Gao","year":"1994","journal-title":"J. Association for Computing Machinery"},{"key":"10.1016\/S0166-218X(01)00225-6_BIB20","doi-asserted-by":"crossref","first-page":"281","DOI":"10.1016\/0020-0190(92)90214-G","article-title":"On the difficulty of Manhattan channel routing","volume":"44","author":"Greenberg","year":"1992","journal-title":"Inform. Process. Lett."},{"key":"10.1016\/S0166-218X(01)00225-6_BIB21","doi-asserted-by":"crossref","first-page":"23","DOI":"10.1109\/TCAD.1985.1270095","article-title":"Channel routing in overlap models","volume":"CAD-4","author":"Hambrusch","year":"1985","journal-title":"IEEE Trans. Comput. Aided Design Integrat. Circuit Systems"},{"key":"10.1016\/S0166-218X(01)00225-6_BIB22","unstructured":"A. Hashimoto, J. Stevens, Wire routing by optimizing channel assignment, Proceedings of the Eigth Design Automation Conference, 1971, pp. 214\u2013224."},{"key":"10.1016\/S0166-218X(01)00225-6_BIB23","doi-asserted-by":"crossref","first-page":"147","DOI":"10.1016\/0196-6774(84)90045-2","article-title":"The NP-completeness column: an ongoing guide","volume":"5","author":"Johnson","year":"1984","journal-title":"J. Algorithms"},{"key":"10.1016\/S0166-218X(01)00225-6_BIB24","doi-asserted-by":"crossref","unstructured":"A.S. LaPaugh, A polynomial time algorithm for optimal routing around a rectangle, Proceedings of the 21st FOCS Symposium, pp. 282\u2013293.","DOI":"10.1109\/SFCS.1980.7"},{"key":"10.1016\/S0166-218X(01)00225-6_BIB25","doi-asserted-by":"crossref","unstructured":"A.S. LaPaugh, VLSI layout algorithms, in: M.J. Atallah (Ed.), Algorithms and Theory of Computation Handbook, CRC Press, Boca Raton, FL, 1999, pp. 23-1\u201323-6.","DOI":"10.1201\/9781584888215-c8"},{"key":"10.1016\/S0166-218X(01)00225-6_BIB26","doi-asserted-by":"crossref","first-page":"230","DOI":"10.1137\/S0895480188161586","article-title":"A 2d\u22121 lower bound for two-layer knock-knee channel routing","volume":"7","author":"Leighton","year":"1994","journal-title":"SIAM J. Discrete Math."},{"year":"1990","series-title":"Combinatorial Algorithms for Integrated Circuit Layout","author":"Lengauer","key":"10.1016\/S0166-218X(01)00225-6_BIB27"},{"key":"10.1016\/S0166-218X(01)00225-6_BIB28","doi-asserted-by":"crossref","first-page":"129","DOI":"10.1016\/0167-9260(85)90029-X","article-title":"A greedy switch-box router","volume":"3","author":"Luk","year":"1985","journal-title":"Integration, VLSI J."},{"key":"10.1016\/S0166-218X(01)00225-6_BIB29","doi-asserted-by":"crossref","unstructured":"M. Marek-Sadowska, E.S. Kuh, General channel-routing algorithm, Proceedings of the IEE (GB), Vol. 130, 1983, pp. 83\u201388.","DOI":"10.1049\/ip-g-1.1983.0016"},{"key":"10.1016\/S0166-218X(01)00225-6_BIB30","doi-asserted-by":"crossref","first-page":"60","DOI":"10.1145\/4904.4994","article-title":"Routing through a rectangle","volume":"33","author":"Mehlhorn","year":"1986","journal-title":"J. Association for Computing Machinery"},{"key":"10.1016\/S0166-218X(01)00225-6_BIB31","article-title":"Manhattan channel routing is NP-complete under truly restricted settings","volume":"6","author":"Middendorf","year":"1996","journal-title":"Chicago J. Theoret. Comput. Sci."},{"key":"10.1016\/S0166-218X(01)00225-6_BIB32","doi-asserted-by":"crossref","unstructured":"R.H. M\u00f6hring, D. Wagner, F. Wagner, VLSI Network Design, in: Handbook in OR & MS: Network Routing, Vol. 8, ed. M.O. Ball, Elsevier, Amsterdam, 1995, pp. 625\u2013712.","DOI":"10.1016\/S0927-0507(05)80112-4"},{"key":"10.1016\/S0166-218X(01)00225-6_BIB33","doi-asserted-by":"crossref","unstructured":"F.P. Preparata, W. Lipski, Jr., Three layers are enough, Proceedings of the 23rd FOCS Symposium, 1982, pp. 350\u2013357.","DOI":"10.1109\/SFCS.1982.47"},{"key":"10.1016\/S0166-218X(01)00225-6_BIB34","unstructured":"A. Recski, 2-layer routing of dense bipartite specifications with vertex disjoint paths and via holes, Report No. 88550-OR, Forschungsinstitut f\u00fcr Diskrete Mathematik, Rheinische Friedrich-Wilhelms-Universit\u00e4t, Bonn, 1989."},{"key":"10.1016\/S0166-218X(01)00225-6_BIB35","doi-asserted-by":"crossref","unstructured":"A. Recski, Minimax results and polynomial algorithms in VLSI routing, in: M. Fiedler, J. Ne\u0161et\u0159il (Eds.), Combinatorics, Graphs, Complexity, Ann. Discrete Math, 1992, pp. 261\u2013273.","DOI":"10.1016\/S0167-5060(08)70641-1"},{"key":"10.1016\/S0166-218X(01)00225-6_BIB36","doi-asserted-by":"crossref","unstructured":"A. Recski, Some polynomially solvable subcases of the detailed routing problem in VLSI design in: U. Zimmermann et al. (Eds.), Operations Research Proceedings, 1996, Springer, Heidelberg, 1997a, 107\u2013110.","DOI":"10.1007\/978-3-642-60744-8_20"},{"key":"10.1016\/S0166-218X(01)00225-6_BIB37","unstructured":"A. Recski, Channel routing in the dogleg-free multilayer Manhattan model, Proceedings of the European Conf. on Circuit Theory and Design, Budapest, Vol. I, 1997b, pp. 39\u201343."},{"key":"10.1016\/S0166-218X(01)00225-6_BIB38","unstructured":"A. Recski, F. Strzyzewski, Vertex-disjoint channel routing on two layers, in: R. Kannan, W.R. Pulleyblank (Eds.), Integer programming and combinatorial optimization, University of Waterloo Press, Waterloo, Ontario, 1990, pp. 397\u2013405."},{"key":"10.1016\/S0166-218X(01)00225-6_BIB39","series-title":"VLSI Systems and Computation","first-page":"153","article-title":"Provably good channel routing algorithms","author":"Rivest","year":"1981"},{"key":"10.1016\/S0166-218X(01)00225-6_BIB40","doi-asserted-by":"crossref","first-page":"503","DOI":"10.1109\/TCAD.1987.1270298","article-title":"Channel routing problem in the knock-knee mode is NP-complete","volume":"CAD-6","author":"Sarrafzadeh","year":"1987","journal-title":"IEEE Trans. Comput. Aided Design Integrat. Circuit Systems"},{"key":"10.1016\/S0166-218X(01)00225-6_BIB41","first-page":"255","article-title":"Compact channel routing of multiterminal nets","volume":"25","author":"Sarrafzadeh","year":"1985","journal-title":"Ann. Discrete Math."},{"key":"10.1016\/S0166-218X(01)00225-6_BIB42","first-page":"155","article-title":"Switchbox routing in the multilayer Manhattan model","volume":"40","author":"Szeszl\u00e9r","year":"1997","journal-title":"Ann. Univ. Sci. Budapest E\u00f6tv\u00f6s Sect. Math"},{"key":"10.1016\/S0166-218X(01)00225-6_BIB43","first-page":"191","article-title":"Optimal routing on narrow channels","volume":"38","author":"Szkaliczki","year":"1994","journal-title":"Period. Polytech. Ser. El. Engrg."},{"key":"10.1016\/S0166-218X(01)00225-6_BIB44","unstructured":"T. Szkaliczki, Ph. D. Thesis, Technical University of Budapest, 1997."},{"key":"10.1016\/S0166-218X(01)00225-6_BIB45","doi-asserted-by":"crossref","first-page":"274","DOI":"10.1137\/S0097539796303123","article-title":"Routing with minimum wire length in the dogleg-free Manhattan model","volume":"29","author":"Szkaliczki","year":"1999","journal-title":"SIAM J. Comput."},{"key":"10.1016\/S0166-218X(01)00225-6_BIB46","doi-asserted-by":"crossref","first-page":"31","DOI":"10.1109\/TCAD.1985.1270096","article-title":"Dogleg channel routing is NP-complete","volume":"CAD-4","author":"Szymanski","year":"1985","journal-title":"IEEE Trans. Comput. Aided Design Integrated Circuit Systems"},{"key":"10.1016\/S0166-218X(01)00225-6_BIB47","doi-asserted-by":"crossref","unstructured":"T. Yoshimura, An efficient channel router, 21st ACM-IEEE Design Automation Conference, 1984, pp. 38\u201344.","DOI":"10.1109\/DAC.1984.1585770"},{"key":"10.1016\/S0166-218X(01)00225-6_BIB48","doi-asserted-by":"crossref","first-page":"25","DOI":"10.1109\/TCAD.1982.1269993","article-title":"Efficient algorithms for channel routing","volume":"CAD-1","author":"Yoshimura","year":"1982","journal-title":"IEEE Trans. Comput. Aided Design Integrat. Circuit Systems"},{"year":"1994","series-title":"Disjoint paths, Report No. 94816, Forschungsinstitut f\u00fcr Diskrete Mathematik","author":"Vygen","key":"10.1016\/S0166-218X(01)00225-6_BIB49"},{"key":"10.1016\/S0166-218X(01)00225-6_BIB50","doi-asserted-by":"crossref","first-page":"163","DOI":"10.1016\/0167-9260(90)90034-X","article-title":"An optimum channel routing algorithm in the restricted wire overlap model","volume":"9","author":"Zhou","year":"1990","journal-title":"Integration, VLSI J."}],"container-title":["Discrete Applied Mathematics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:S0166218X01002256?httpAccept=text\/xml","content-type":"text\/xml","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:S0166218X01002256?httpAccept=text\/plain","content-type":"text\/plain","content-version":"vor","intended-application":"text-mining"}],"deposited":{"date-parts":[[2025,9,28]],"date-time":"2025-09-28T11:57:08Z","timestamp":1759060628000},"score":1,"resource":{"primary":{"URL":"https:\/\/linkinghub.elsevier.com\/retrieve\/pii\/S0166218X01002256"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2001,11]]},"references-count":50,"journal-issue":{"issue":"1-3","published-print":{"date-parts":[[2001,11]]}},"alternative-id":["S0166218X01002256"],"URL":"https:\/\/doi.org\/10.1016\/s0166-218x(01)00225-6","relation":{},"ISSN":["0166-218X"],"issn-type":[{"type":"print","value":"0166-218X"}],"subject":[],"published":{"date-parts":[[2001,11]]},"assertion":[{"value":"Elsevier","name":"publisher","label":"This article is maintained by"},{"value":"Some polynomially solvable subcases of the detailed routing problem in VLSI design","name":"articletitle","label":"Article Title"},{"value":"Discrete Applied Mathematics","name":"journaltitle","label":"Journal Title"},{"value":"https:\/\/doi.org\/10.1016\/S0166-218X(01)00225-6","name":"articlelink","label":"CrossRef DOI link to publisher maintained version"},{"value":"converted-article","name":"content_type","label":"Content Type"},{"value":"Copyright \u00a9 2001 Elsevier Science B.V. All rights reserved.","name":"copyright","label":"Copyright"}]}}