计算机工程与应用Issue(1)：21-25,5.DOI:10.3778/j.issn.1002-8331.1402-0274
基于图论模型的一类集成电路布线算法
Graph theoretic approach for routing problem in VLSI
摘要
Abstract
For a channel in 2-layer Manhattan model, this paper aims at interconnecting the terminals of each net by wires such that the circuit elements and the interconnecting wires are embedded into two planar layers by the methods of graph theory. Furthermore, the width(number of tracks required for routing)of a channel should be minimized. The constraints of a channel routing problem can be represented by a Horizontal Constraint Graph(HCG)and a Vertical Constraint Graph (VCG). Considering the two constraints, the paper improves the upper bound, it shows that this algorithm is better than the best known algorithm.关键词
有向图/通道布线/最短路径Key words
directed graph/channel routing/shorting routing path分类
数理科学引用本文复制引用
耿显亚,许峰..基于图论模型的一类集成电路布线算法[J].计算机工程与应用,2015,(1):21-25,5.基金项目
国家自然科学基金（No.11401008）；安徽省教育厅自然科学基金重点项目（No.KJ2014A064）；安徽理工大学硕博基金（No.11167）。 （）
