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

^*此作品的通信作者

研究成果: 雜誌貢獻 › 期刊論文 › 同行評審

摘要

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.

原文	英語
頁（從 - 到）	673-683
頁數	11
期刊	Journal of the Chinese Institute of Engineers, Transactions of the Chinese Institute of Engineers,Series A/Chung-kuo Kung Ch'eng Hsuch K'an
卷	13
發行號	6
DOIs	https://doi.org/10.1080/02533839.1990.9677299
出版狀態	已發佈 - 1990 9月

ASJC Scopus subject areas

一般工程

存取文件

10.1080/02533839.1990.9677299

其它文件與鏈接

引用此

@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

摘要

ASJC Scopus subject areas

存取文件

其它文件與鏈接

指紋

引用此