A Topological Sorting Algorithm For Three-Layer Channel Routing

Kuo En Chang; Tin Hung Lai; Wu Shiung Feng

doi:10.1080/02533839.1990.9677299

A Topological Sorting Algorithm For Three-Layer Channel Routing

Kuo En Chang^*, Tin Hung Lai, Wu Shiung Feng

^*Corresponding author for this work

Research output: Contribution to journal › Article › peer-review

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 language	English
Pages (from-to)	673-683
Number of pages	11
Journal	Journal of the Chinese Institute of Engineers, Transactions of the Chinese Institute of Engineers,Series A/Chung-kuo Kung Ch'eng Hsuch K'an
Volume	13
Issue number	6
DOIs	https://doi.org/10.1080/02533839.1990.9677299
Publication status	Published - 1990 Sept

Keywords

Channel routing
Topological sorting

ASJC Scopus subject areas

General Engineering

Access to Document

10.1080/02533839.1990.9677299

Cite this

@article{e73a876782fe44d0b50d176ebaa81dea,

title = "A Topological Sorting Algorithm For Three-Layer Channel Routing",

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{\textquoteright}s difficult example are used as test problems.",

keywords = "Channel routing, Topological sorting",

author = "Chang, {Kuo En} and Lai, {Tin Hung} and Feng, {Wu Shiung}",

note = "Funding Information: This work was supported by the National Science Council, Taipei, Taiwan, the Republic of China, under Contract No. NSC78-0404-E002-46.",

year = "1990",

month = sep,

doi = "10.1080/02533839.1990.9677299",

language = "English",

volume = "13",

pages = "673--683",

journal = "Journal of the Chinese Institute of Engineers, Transactions of the Chinese Institute of Engineers,Series A/Chung-kuo Kung Ch'eng Hsuch K'an",

issn = "0253-3839",

publisher = "Chinese Institute of Engineers",

number = "6",

}

TY - JOUR

T1 - A Topological Sorting Algorithm For Three-Layer Channel Routing

AU - Chang, Kuo En

AU - Lai, Tin Hung

AU - Feng, Wu Shiung

N1 - Funding Information: This work was supported by the National Science Council, Taipei, Taiwan, the Republic of China, under Contract No. NSC78-0404-E002-46.

PY - 1990/9

Y1 - 1990/9

N2 - 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.

AB - 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.

KW - Channel routing

KW - Topological sorting

UR - http://www.scopus.com/inward/record.url?scp=0025510670&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=0025510670&partnerID=8YFLogxK

U2 - 10.1080/02533839.1990.9677299

DO - 10.1080/02533839.1990.9677299

M3 - Article

AN - SCOPUS:0025510670

SN - 0253-3839

VL - 13

SP - 673

EP - 683

JO - Journal of the Chinese Institute of Engineers, Transactions of the Chinese Institute of Engineers,Series A/Chung-kuo Kung Ch'eng Hsuch K'an

JF - Journal of the Chinese Institute of Engineers, Transactions of the Chinese Institute of Engineers,Series A/Chung-kuo Kung Ch'eng Hsuch K'an

IS - 6

ER -

A Topological Sorting Algorithm For Three-Layer Channel Routing

Abstract

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this