Constrained via minimization for three-layer routing

Kuo-En Chang, H. F. Jyu, W. S. Feng

研究成果: 雜誌貢獻文章

6 引文 斯高帕斯(Scopus)

摘要

The constrained via minimization problem for VLSI three-layer routing is the problem of determining which layers can be used for routing the wire segments in the interconnections of nets so that the number of vias is minimized. This problem has been shown to be NP-complete15. In this paper, this problem is first transformed to the contractibility problem of a three-colourable graph, then an heuristic algorithm is proposed on the basis of the graph contractability model. From experimental results, the algorithm proves faster and more efficient at generating very good results. For a typical case, the number of vias can be reduced by about 30%.

原文英語
頁(從 - 到)346-354
頁數9
期刊Computer-Aided Design
21
發行號6
DOIs
出版狀態已發佈 - 1989 一月 1

ASJC Scopus subject areas

  • Computer Science Applications
  • Computer Graphics and Computer-Aided Design
  • Industrial and Manufacturing Engineering

指紋 深入研究「Constrained via minimization for three-layer routing」主題。共同形成了獨特的指紋。

  • 引用此