基于图论模型的一类集成电路布线算法

杨利霞

基于图论模型的一类集成电路布线算法

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