A Topological Sorting Algorithm For Three-Layer Channel Routing

Kuo En Chang, Tin Hung Lai, Wu Shiung Feng

Research output: Contribution to journalArticle

Abstract

Three-layer channel routing is an important problem in VLSI layout. In this paper, we present a topological sorting algorithm to determine the topological order on nets depending on the operations of the vertical con-.straint graph (VCG) and the horizontal constraint graph (HCG). According to the order, the base router can finish the connections of all nets. In the algorithm, the HVH mode is assumed, and some examples including Deutsch’s difficult example are used as test problems.

Original languageEnglish
Pages (from-to)673-683
Number of pages11
JournalJournal of the Chinese Institute of Engineers, Transactions of the Chinese Institute of Engineers,Series A/Chung-kuo Kung Ch'eng Hsuch K'an
Volume13
Issue number6
DOIs
Publication statusPublished - 1990 Sep

Keywords

  • Channel routing
  • Topological sorting

ASJC Scopus subject areas

  • Engineering(all)

Fingerprint Dive into the research topics of 'A Topological Sorting Algorithm For Three-Layer Channel Routing'. Together they form a unique fingerprint.

  • Cite this