Channel Density Minimization by Pin Permutation

Yang Cai, D. F. Wong, Jason Cong

Research output: Contribution to journalJournal articlepeer-review


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 languageEnglish
Pages (from-to)171-183
Number of pages13
JournalVLSI Design
Issue numberSpecial Issue
Publication statusPublished - Jan 1994

Scopus Subject Areas

  • Hardware and Architecture
  • Computer Graphics and Computer-Aided Design
  • Electrical and Electronic Engineering

User-Defined Keywords

  • VLSI
  • Circuit layout
  • Channel routing
  • Pin assignment
  • Pin permutation


Dive into the research topics of 'Channel Density Minimization by Pin Permutation'. Together they form a unique fingerprint.

Cite this