DocumentCode
1899909
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
Volume
6
fYear
1998
fDate
31 May-3 Jun 1998
Firstpage
254
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;
fLanguage
English
Publisher
ieee
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
Type
conf
DOI
10.1109/ISCAS.1998.705259
Filename
705259
Link To Document