A graph theoretic approach to feed-through pin assignment

Yao Ping Chen, D. F. Wong

Research output: Contribution to journalArticlepeer-review


We study in this paper the feed-through pin assignment problem for cell-based design that assigns global nets to feed-through cells or implicit feed-through ports. On a single row, for a restricted permutation of global nets, we develop a graph theoretic approach for optimally minimizing the density of the channel above (below) the row subject to the bound on the density of the channel below (above) the row. Based on this technique, an approach for iteratively improving multiple row feed-through pin assignment can be developed. We show that our approach is also applicable to the design style in which there is an over-the-cell feed-through layer.

Original languageEnglish (US)
Pages (from-to)147-158
Number of pages12
JournalIntegration, the VLSI Journal
Issue number2
StatePublished - Dec 1997
Externally publishedYes


  • Feed-through pin
  • Graphy theory
  • Routing
  • Standard cell

ASJC Scopus subject areas

  • Software
  • Hardware and Architecture
  • Electrical and Electronic Engineering


Dive into the research topics of 'A graph theoretic approach to feed-through pin assignment'. Together they form a unique fingerprint.

Cite this