Takeshi Yoshimura*, Ernest S. Kuh

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

302 Citations (Scopus)


In the layout design of LSI chips, channel routing is one of the key problems. The problem is to route a specified net list between two rows of terminals across a two-layer channel. Nets are routed with horizontal segments on one layer and vertical segments on the other. Connections between two layers are made through via holes. Two new algorithms are proposed. These algorithms merge nets instead of assigning horizontal tracks to individual nets. The algorithms were coded in Fortran and implemented on a VAX 11/780 computer. Experimental results are quite encouraging. Both programs generated optimal solutions in 6 out of 8 cases, using examples in previously published papers. The computation times of the algorithms for a typical channel (300 terminals, 70 nets) are 1. 0 and 2. 1 s, respectively.

Original languageEnglish
Pages (from-to)25-35
Number of pages11
JournalIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems
Issue number1
Publication statusPublished - 1982 Jan
Externally publishedYes

ASJC Scopus subject areas

  • Computational Theory and Mathematics
  • Computer Science Applications
  • Hardware and Architecture
  • Electrical and Electronic Engineering


Dive into the research topics of 'EFFICIENT ALGORITHMS FOR CHANNEL ROUTING.'. Together they form a unique fingerprint.

Cite this