Abstract
We present in this paper 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. This compares favorably with the previously known near-optimal algorithm presented in [6] that runs in superlinear time. Our algorithm has important applications in hierarchical layout design of intergrated circuits. We also show that the problem of minimizing wire length by permuting terminals is NP-hard in the strong sense.
| Original language | English (US) |
|---|---|
| Pages (from-to) | 171-183 |
| Number of pages | 13 |
| Journal | VLSI Design |
| Volume | 2 |
| Issue number | 2 |
| DOIs | |
| State | Published - 1994 |
| Externally published | Yes |
Keywords
- Channel routing
- Circuit layout
- Pin assignment
- Pin permutation
- VLSI
ASJC Scopus subject areas
- Hardware and Architecture
- Computer Graphics and Computer-Aided Design
- Electrical and Electronic Engineering
Fingerprint
Dive into the research topics of 'Channel Density Minimization by Pin Permutation'. Together they form a unique fingerprint.Cite this
- APA
- Standard
- Harvard
- Vancouver
- Author
- BIBTEX
- RIS