{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T11:05:23Z","timestamp":1740135923494,"version":"3.37.3"},"reference-count":0,"publisher":"Wiley","issue":"4","license":[{"start":{"date-parts":[[2000,1,1]],"date-time":"2000-01-01T00:00:00Z","timestamp":946684800000},"content-version":"vor","delay-in-days":1593,"URL":"http:\/\/creativecommons.org\/licenses\/by\/3.0\/"}],"funder":[{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["CDA-9216202"],"award-info":[{"award-number":["CDA-9216202"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["VLSI Design"],"published-print":{"date-parts":[[1998,1]]},"abstract":"<jats:p>Every knock\u2010knee layout is four\u2010layer wirable. However, there are knock\u2010knee layouts\nthat cannot be wired in less than four layers. While it is easy to determine whether a\nknock\u2010knee layout is one\u2010layer wirable or two\u2010layer wirable, the problem of determining\nthree\u2010layer wirability of knock\u2010knee layouts is NP\u2010complete. A knock\u2010knee layout may\nbe stretched vertically (horizontally) by introducing empty rows (columns) so that it can\nbe wired in fewer than four layers. In this paper we discuss two different types of\nstretching schemes. It is known that under these two stretching schemes, any knock\u2010knee\nlayout is three\u2010layer wirable by stretching it up to (4\/3) of the knock\u2010knee layout\narea (upper bound). We show that there are knock\u2010knee layouts that when stretched\nand wired in three layers under scheme I (II) require at least 1.2 (1.07563) of the original\nlayout area. Our lower bound for the area increase factor can be used to guide the\nsearch for effective stretching\u2010based dynamic programming three\u2010layer wiring algorithms\nsimilar to the one presented in [8].<\/jats:p>","DOI":"10.1155\/1998\/14757","type":"journal-article","created":{"date-parts":[[2007,9,18]],"date-time":"2007-09-18T12:57:36Z","timestamp":1190120256000},"page":"365-383","source":"Crossref","is-referenced-by-count":0,"title":["On Ensuring Multilayer Wirability by Stretching Layouts"],"prefix":"10.1155","volume":"7","author":[{"given":"Teofilo F.","family":"Gonzalez","sequence":"first","affiliation":[]},{"given":"Si-Qing","family":"Zheng","sequence":"additional","affiliation":[]}],"member":"311","published-online":{"date-parts":[[1995,8,22]]},"container-title":["VLSI Design"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/downloads.hindawi.com\/archive\/1998\/014757.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/pdf\/10.1155\/1998\/14757","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,8,7]],"date-time":"2024-08-07T23:01:49Z","timestamp":1723071709000},"score":1,"resource":{"primary":{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/10.1155\/1998\/14757"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1995,8,22]]},"references-count":0,"journal-issue":{"issue":"4","published-print":{"date-parts":[[1998,1]]}},"alternative-id":["10.1155\/1998\/14757"],"URL":"https:\/\/doi.org\/10.1155\/1998\/14757","archive":["Portico"],"relation":{},"ISSN":["1065-514X","1563-5171"],"issn-type":[{"type":"print","value":"1065-514X"},{"type":"electronic","value":"1563-5171"}],"subject":[],"published":{"date-parts":[[1995,8,22]]}}}