Title :
A heuristic algorithm to solve constrained via minimization for three-layer routing problems
Author :
Takahashi, Kazuhiro ; Watanabe, Toshimnsa
Author_Institution :
Fac. of Eng., Hiroshima Univ., Japan
fDate :
31 May-3 Jun 1998
Abstract :
The constrained via minimization problem is the problem of minimizing the number of vias by changing the layer assignment of nets whose routing are given. It is already known that the problem is NP-complete even for three layer routing. The subject of the paper is to propose a heuristic algorithm VMBF, based an the breadth-first search, to solve the constrained via minimization for the three layer routing problem. Experimental results are provided to show the capability of the proposed algorithm
Keywords :
VLSI; circuit layout CAD; crosstalk; graph theory; integrated circuit layout; minimisation; network routing; printed circuit layout; NP-complete problem; VMBF algorithm; breadth-first search; constrained via minimization; heuristic algorithm; layer assignment; three-layer routing problems; Circuits and systems; Crosstalk; Heuristic algorithms; Minimization methods; Production; Routing; Systems engineering and theory; Very large scale integration; Wire; Wiring;
Conference_Titel :
Circuits and Systems, 1998. ISCAS '98. Proceedings of the 1998 IEEE International Symposium on
Conference_Location :
Monterey, CA
Print_ISBN :
0-7803-4455-3
DOI :
10.1109/ISCAS.1998.705259
