{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2022,4,4]],"date-time":"2022-04-04T15:19:47Z","timestamp":1649085587742},"reference-count":0,"publisher":"World Scientific Pub Co Pte Lt","issue":"03","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Int. J. Comput. Geom. Appl."],"published-print":{"date-parts":[[1993,9]]},"abstract":"<jats:p> We present a new channel routing algorithm in the knock-knee mode that produces for dense problems area-optimal layouts with minimum total wire length and [Formula: see text] bends (n number of nets), where the total number of bends is at most d\u22122 (d density) more than the minimum. The running time is [Formula: see text]. It thus improves the algorithm in Formann et al.,<jats:sup>3<\/jats:sup> which determines area-optimal layouts with minimum total wire length in [Formula: see text] time, where the number of bends is \u03a9(n<jats:sup>2<\/jats:sup>). Moreover, the algorithm can be modified so as to guarantee three-layer wirable layouts, where the total wire length is at most n\u22122 more than the minimum. The approach we use is completely different from all previously known algorithms. It is based on the notion of cycle graphs introduced in this paper. <\/jats:p>","DOI":"10.1142\/s0218195993000178","type":"journal-article","created":{"date-parts":[[2004,11,23]],"date-time":"2004-11-23T03:29:30Z","timestamp":1101180570000},"page":"269-289","source":"Crossref","is-referenced-by-count":5,"title":["OPTIMAL ROUTING THROUGH DENSE CHANNELS"],"prefix":"10.1142","volume":"03","author":[{"given":"DOROTHEA","family":"WAGNER","sequence":"first","affiliation":[{"name":"Fachbereich Mathematik, Technische Universit\u00e4t Berlin, Stra\u00dfe des 17. Juni 136, 10623 Berlin, Germany"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"219","published-online":{"date-parts":[[2011,11,20]]},"container-title":["International Journal of Computational Geometry &amp; Applications"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.worldscientific.com\/doi\/pdf\/10.1142\/S0218195993000178","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,8,7]],"date-time":"2019-08-07T00:31:03Z","timestamp":1565137863000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.worldscientific.com\/doi\/abs\/10.1142\/S0218195993000178"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1993,9]]},"references-count":0,"journal-issue":{"issue":"03","published-online":{"date-parts":[[2011,11,20]]},"published-print":{"date-parts":[[1993,9]]}},"alternative-id":["10.1142\/S0218195993000178"],"URL":"https:\/\/doi.org\/10.1142\/s0218195993000178","relation":{},"ISSN":["0218-1959","1793-6357"],"issn-type":[{"value":"0218-1959","type":"print"},{"value":"1793-6357","type":"electronic"}],"subject":[],"published":{"date-parts":[[1993,9]]}}}