Abstract | ||
---|---|---|
A study is made of the problem of routing region definition and ordering in VLSI building-block layout design. An algorithm to decompose the routing area into straight channels and rectangular switchboxes corresponding to line segments in the routing structure of the placement such that the number of switchboxes is minimized, is presented. The algorithm is based on a graph-theory approach that makes use of an efficient polynomial time algorithm for computing minimum clique covers of triangulated graphs. Experimental results indicate that the algorithm performs well. For all the test problems considered, the algorithm consistently outperformed a previous known greedy algorithm, and it produced optimal solutions in all but one case |
Year | DOI | Venue |
---|---|---|
1991 | 10.1109/43.103498 | Computer-Aided Design of Integrated Circuits and Systems, IEEE Transactions |
Keywords | DocType | Volume |
efficient polynomial time algorithm,optimal solution,routing area,minimum clique,routing structure,greedy algorithm,VLSI building-block layout design,graph-theory approach,experimental result,switchbox definition,rectangular switchboxes | Journal | 10 |
Issue | ISSN | Citations |
12 | 0278-0070 | 5 |
PageRank | References | Authors |
0.55 | 11 | 2 |
Name | Order | Citations | PageRank |
---|---|---|---|
Cai, Y. | 1 | 5 | 0.55 |
D. F. Wong | 2 | 5 | 0.55 |