An optimum channel-routing algorithm for polycell layouts of integrated circuits

B. W. Kernighan, D. G. Schweikert, G. Persky

Research output: Contribution to journalConference articlepeer-review

64 Scopus citations


This paper presents an algorithm for finding optimum routings for interconnection paths in a channel between two parallel rows of circuit cells. A routing algorithm thus need only avoid overlapping collinear horizontal segments of different nets, and avoid overlapping collinear vertical segments, to achieve a physically acceptable routing. The algorithm, although based on branch and bound, has provided optimum routings for circuits with 50 to 60 nets in a minute or two of computing.

Original languageEnglish (US)
Article number803997
Pages (from-to)50-59
Number of pages10
JournalProceedings - Design Automation Conference
StatePublished - Jun 25 1973
Externally publishedYes
Event10th Design Automation Workshop, DAC 1973 - Portland, United States
Duration: Jun 25 1973Jun 27 1973

All Science Journal Classification (ASJC) codes

  • Computer Science Applications
  • Control and Systems Engineering
  • Electrical and Electronic Engineering
  • Modeling and Simulation


Dive into the research topics of 'An optimum channel-routing algorithm for polycell layouts of integrated circuits'. Together they form a unique fingerprint.

Cite this