Browsing by Author "Shew, PW"

Now showing 1 - 2 of 2

Planar constrained terminals over-the-cell router
(1997-03-01)
Shew, PW
;
Hsiao, PY
;
資訊工程學系
;
Department of Computer Science
The authors present a new routing model for over-the-cell channel routing. A graph theoretical algorithm is then proposed to solve the new problem, The algorithm has a complexity of O(nk(2)), where n is the number of nets and k is the number of columns in the channel. It achieved a routing area reduction of 71.5% for the PRIMARY 1 benchmark example from MCNC, using three-layer over-the-cell routing. To resolve a sub-problem, the authors also present an O(m nu) algorithm to find the maximum weight independent chord set in a circle graph with m chords incident to nu vertices, where two chords may share a common vertex.
Planar constrained terminals over-the-cell router
(1997-03-01)
Shew, PW
;
Hsiao, PY
;
資訊工程學系
;
Department of Computer Science
The authors present a new routing model for over-the-cell channel routing. A graph theoretical algorithm is then proposed to solve the new problem, The algorithm has a complexity of O(nk(2)), where n is the number of nets and k is the number of columns in the channel. It achieved a routing area reduction of 71.5% for the PRIMARY 1 benchmark example from MCNC, using three-layer over-the-cell routing. To resolve a sub-problem, the authors also present an O(m nu) algorithm to find the maximum weight independent chord set in a circle graph with m chords incident to nu vertices, where two chords may share a common vertex.