An optimal channel pin assignment algorithm

Y. Cai, D.F. Wong

Research output: Chapter in book/report/conference proceedingConference proceeding

3 Citations (Scopus)


A study is made of the channel pin assignment problem subject to both position and order constraints. The authors show that the problem is NP-hard in general and present a polynomial time optimal algorithm for an important case where the relative orderings of the terminals are completely fixed. They extend their algorithm to solve the problem for the case where there are also separation constraints between some pairs of consecutive terminals optimally in polynomial time. A discussion is presented of how the algorithm can be incorporated into standard cell and building-block layout design systems. Experimental results indicate that by allowing movable terminals, substantial reductions in channel density can be obtained.
Original languageEnglish
Title of host publication1990 IEEE International Conference on Computer-Aided Design. Digest of Technical Papers
Number of pages4
ISBN (Print)0818620552
Publication statusPublished - 15 Nov 1990
Event1990 IEEE International Conference on Computer-Aided Design, ICCAD 1990 - Santa Clara, United States
Duration: 11 Nov 199015 Nov 1990

Publication series

NameIEEE International Conference on Computer-Aided Design


Conference1990 IEEE International Conference on Computer-Aided Design, ICCAD 1990
Country/TerritoryUnited States
CitySanta Clara
Internet address

User-Defined Keywords

  • Routing
  • Polynomials
  • Algorithm design and analysis
  • Very large scale integration
  • Circuits
  • Pins


Dive into the research topics of 'An optimal channel pin assignment algorithm'. Together they form a unique fingerprint.

Cite this