標題: Planar constrained terminals over-the-cell router
作者: Shew, PW
Hsiao, PY
資訊工程學系
Department of Computer Science
關鍵字: over-the-cell routing;maximum weight independent chord set;circle graph;VLSI
公開日期: 1-三月-1997
摘要: 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.
URI: http://dx.doi.org/10.1049/ip-cdt:19971157
http://hdl.handle.net/11536/698
ISSN: 1350-2387
DOI: 10.1049/ip-cdt:19971157
期刊: IEE PROCEEDINGS-COMPUTERS AND DIGITAL TECHNIQUES
Volume: 144
Issue: 2
起始頁: 121
結束頁: 126
顯示於類別:期刊論文


文件中的檔案:

  1. A1997XC46300009.pdf