An Efficient and Fast Algorithm for Routing Over the Cells

Research output: Contribution to journalArticlepeer-review


A linear time algorithm for routing over the cells is presented. The algorithm tries to reduce maximum channel density by routing some connections over the cells. The algorithm first defines a new scheme for channel representation and formulates the problem based on an intersection graph derived from the new scheme. Then, a feasible independent set of the intersection graph is found for routing some subnets over the cells. The algorithm is implemented and evaluated with several well known benchmarks. In comparison with previous research, our results are satisfactory, and the algorithm takes substantially less CPU time than those of previous works. For Deutsch’s difficult example, the previous algorithms take about 29.25 seconds on an average but our new algorithm needs only 5.6 seconds.

Original languageEnglish
Pages (from-to)1-10
Number of pages10
JournalVLSI Design
Issue number1
Publication statusPublished - 1996


  • Channel routing
  • and intersection graph
  • independant set
  • routing over the cells

ASJC Scopus subject areas

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


Dive into the research topics of 'An Efficient and Fast Algorithm for Routing Over the Cells'. Together they form a unique fingerprint.

Cite this