DOGLEG CHANNEL ROUTING IS NP-COMPLETE

被引：93

作者：

SZYMANSKI, TG

机构：

[1] AT&T Bell Lab, Murray Hill, NJ,, USA, AT&T Bell Lab, Murray Hill, NJ, USA

来源：

IEEE TRANSACTIONS ON COMPUTER-AIDED DESIGN OF INTEGRATED CIRCUITS AND SYSTEMS | 1985年 / 4卷 / 01期

关键词：

COMPUTER AIDED DESIGN - COMPUTER PROGRAMMING - Algorithms;

D O I：

10.1109/TCAD.1985.1270096

中图分类号：

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

学科分类号：

0812 ;

摘要：

Interconnecting two rows of points across an intervening channel is an important problem in the design of LSI circuits. The most common methodology for producing such interconnections uses two orthogonal layers of parallel conductors and allows wires to 'dogleg' arbitrarily. Although effective heuristic procedures are available for routing channels with this methodology, no efficient optimal algorithm has yet been discovered for the general case problem. The author shows that such an algorithm is unlikely to exist by establishing that this problem is NP-complete.

引用

页码：31 / 41

页数：11

共 13 条

[1]

BROWN DJ, 1981, OCT P CMU C VLSI SYS, P178

[2]

DEUTSCH DN, 1976, 19TH P DES AUT C IEE, P425

[3]

DOLEV D, 1981, 13TH P ANN ACM S THE, P312

[4]

Garey Michael R., 1979, COMPUTERS INTRACTABI

[5]

Hashimoto A., 1971, P 8 DES AUT WORKSH, P155

[6]

LAPAUGH AS, 1980, THESIS MIT

[7]

LEIGHTON FT, 1982, MIT VLSI8271 MEM

[8]

LEISERSON CE, 1983, SIAM J COMPUT, V12, P447, DOI 10.1137/0212029

[9]

PINTER RY, 1981, OCT P CMU C VLSI SYS, P160

[10]

RIVEST RL, 1981, OCT P CMU C VLSI SYS, P153

← 1 2 →