{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,8,8]],"date-time":"2024-08-08T05:10:02Z","timestamp":1723093802512},"reference-count":0,"publisher":"Wiley","issue":"1","license":[{"start":{"date-parts":[[2000,1,1]],"date-time":"2000-01-01T00:00:00Z","timestamp":946684800000},"content-version":"vor","delay-in-days":2528,"URL":"http:\/\/creativecommons.org\/licenses\/by\/3.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["VLSI Design"],"published-print":{"date-parts":[[1994,1]]},"abstract":"The use of programmable logic cells in VLSI design allows the terminals on these cells to be interchanged since\ntheir geometrics are programmable. Recently, many exact algorithms and heuristics have been proposed for\nchannel routing with interchangeable terminals [18, 25, 4, 11, 12, 20, 17, 3]. Various optimization problems have\nalso been shown to be NP<\/jats:italic>\u2014hard<\/jats:italic> [25, 23]. In this paper, we consider channels with exits. Let m<\/jats:italic>, D<\/jats:italic> be the number\nof terminals in the channel and the maximum number of terminals on a net, respectively. We present an O(m)<\/jats:italic>\nalgorithm that obtains optimal density for channels with exits that have one cell on each side. The existing\nalgorithm for this problem [5] guarantees only an approximate density. Moreover, if one of the two cells has\nfixed terminals, we show that the density minimization problem is NP\u2010hard. The latter problem was introduced\nin [5]. For instances with any number of cells we present an O(m)<\/jats:italic> time algorithm for the via minimization problem,\nan O(m<\/jats:italic>2<\/jats:sup> \u00b7 D<\/jats:italic>) algorithm for the problem of finding a maximum planar subset of nets in a channel, and an O(m)<\/jats:italic>\nalgorithm to determine whether the channel adopts external\u2010internal layout. Also for the special case where there\nexists one cell per side, we present an alternative algorithm that finds a maximum planar set of nets in O(m)<\/jats:italic>\ntime.<\/jats:p>","DOI":"10.1155\/1994\/48137","type":"journal-article","created":{"date-parts":[[2007,9,18]],"date-time":"2007-09-18T12:56:35Z","timestamp":1190120195000},"page":"51-68","source":"Crossref","is-referenced-by-count":1,"title":["On Channel Routing Problems WithInterchangeable Terminals"],"prefix":"10.1155","volume":"2","author":[{"given":"Spyros","family":"Tragoudas","sequence":"first","affiliation":[]}],"member":"311","published-online":{"date-parts":[[1993,1,29]]},"container-title":["VLSI Design"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/downloads.hindawi.com\/archive\/1994\/048137.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/downloads.hindawi.com\/journals\/vlsi\/1994\/048137.xml","content-type":"application\/xml","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/pdf\/10.1155\/1994\/48137","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,8,8]],"date-time":"2024-08-08T04:44:17Z","timestamp":1723092257000},"score":1,"resource":{"primary":{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/10.1155\/1994\/48137"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1993,1,29]]},"references-count":0,"journal-issue":{"issue":"1","published-print":{"date-parts":[[1994,1]]}},"alternative-id":["10.1155\/1994\/48137"],"URL":"https:\/\/doi.org\/10.1155\/1994\/48137","archive":["Portico"],"relation":{},"ISSN":["1065-514X","1563-5171"],"issn-type":[{"type":"print","value":"1065-514X"},{"type":"electronic","value":"1563-5171"}],"subject":[],"published":{"date-parts":[[1993,1,29]]}}}