LAYER ASSIGNMENT PROBLEM FOR 3-LAYER ROUTING

被引：20

作者：

CHANG, KC ^{[1
]}

DU, HC ^{[1
]}

机构：

[1] UNIV MINNESOTA,DEPT COMP SCI,MINNEAPOLIS,MN 55455

来源：

IEEE TRANSACTIONS ON COMPUTERS | 1988年 / 37卷 / 05期

关键词：

COMPUTER PROGRAMMING - Algorithms;

D O I：

10.1109/12.4616

中图分类号：

TP3 [计算技术、计算机技术];

学科分类号：

0812 ;

摘要：

The layer assignment problem for interconnect is the problem of determining which layers should be used for wiring the signal nets so that the number of vias is minimized. The problem is often referred to as the via minimization problem. The problem is considered for three-layer routing, concentrating on one version called the constrained via minimization (CVM3) problem. It is shown that the CVM3 problem is NP-complete and a heuristic algorithm is proposed. The experimental results show that the proposed algorithm is efficient and generates fairly good solutions.

引用

页码：625 / 632

页数：8

共 23 条

[1] EFFICIENT ALGORITHMS FOR LAYER ASSIGNMENT PROBLEM [J].

CHANG, KC ;

DU, DHC .

IEEE TRANSACTIONS ON COMPUTER-AIDED DESIGN OF INTEGRATED CIRCUITS AND SYSTEMS, 1987, 6 (01) :67-78

[2]

CHANG KC, TR8533 U MINN DEP CO

[3]

CHEN RW, 1983, IEEE T CIRCUITS SYST, V30, P284, DOI 10.1109/TCS.1983.1085357

[4]

CHEN RW, 1982, P ISCAS, P968

[5]

CHEN RW, 1981, 15TH AS C CIRC SYST, P22

[6]

CHEN YK, 1984, IEEE T COMPUT AID D, V3, P156, DOI 10.1109/TCAD.1984.1270070

[7]

CIESIELSKI MJ, 1981, 18TH P DES AUT C, P733

[8]

DEO N, 1974, GRAPH THEORY APPLICA

[9]

DU HC, 1984, TR8420 U MINN DEP CO

[10] COMPLEXITY OF NEAR-OPTIMAL GRAPH COLORING [J].

GAREY, MR ;

JOHNSON, DS .

JOURNAL OF THE ACM, 1976, 23 (01) :43-49

← 1 2 3 →