DocumentCode
1663219
Title
Channel density minimization by pin permutation
Author
Cai, Yang ; Wong, D.F.
Author_Institution
Dept. of Comput. Sci., Texas Univ., Austin, TX, USA
fYear
1992
Firstpage
378
Lastpage
382
Abstract
A linear-time optimal algorithm for minimizing the density of a channel (with exits) by permuting the terminals on the two sides of the channel is presented. It compares favorably with the near-optimal algorithm of J. Cong and K.-Y. Khoo (1991) that runs in superlinear time. The present algorithm has important applications in hierarchical layout design of integrated circuits. In addition, it is shown that the problem of minimizing wire length by permuting terminals is NP-hard in the strong sense
Keywords
VLSI; circuit layout CAD; computational complexity; NP-hard; VLSI; channel density minimisation; hierarchical layout design; integrated circuits; linear-time optimal algorithm; near-optimal algorithm; pin permutation; superlinear time; Algorithm design and analysis; Circuits; Delta modulation; Minimization; Polynomials; Routing; Scholarships; Very large scale integration; Wire;
fLanguage
English
Publisher
ieee
Conference_Titel
Computer Design: VLSI in Computers and Processors, 1992. ICCD '92. Proceedings, IEEE 1992 International Conference on
Conference_Location
Cambridge, MA
Print_ISBN
0-8186-3110-4
Type
conf
DOI
10.1109/ICCD.1992.276294
Filename
276294
Link To Document