圖論在通道布線中的應(yīng)用和Wiener指數(shù)問題研究.pdf

1、通道布線問題是超大規(guī)模集成電路中的一個(gè)關(guān)鍵問題。雙層通道布線[1,2]的線網(wǎng)結(jié)構(gòu)可以用垂直約束和水平約束進(jìn)行描述，鑒于該特殊結(jié)構(gòu)，能夠?qū)D論的思想運(yùn)用到雙層通道布線中。本文在前人的基礎(chǔ)上，對(duì)垂直約束圖中含有圈的情況進(jìn)行了討論，其中在含有一個(gè)圈的通道布線問題中，主要利用尋找并消除臨界網(wǎng)的方法給出布線的一個(gè)新的算法，該算法能夠得到軌道的一個(gè)下界。在含有多個(gè)圈時(shí)，主要從結(jié)點(diǎn)的兩類約束圖入手來研究布線算法，通過對(duì)垂直約束圖中含有有向圈的一類通道

2、布線問題進(jìn)行研究，設(shè)計(jì)出包含一對(duì)和兩對(duì)空結(jié)點(diǎn)情況下的布線算法，該方法能夠得到更好的軌道高度。并且對(duì)具體的布線過程進(jìn)行了詳細(xì)的描述。
　　Wiener指數(shù)[3]也是圖論的一個(gè)重要的應(yīng)用，它在理論化學(xué)中運(yùn)用十分廣泛。Wiener指數(shù)指一個(gè)圖中所有點(diǎn)對(duì)的距離之和，用如下式子表示:W(G)=∑{u,v}∈VGdG(u，v)=1/2∑v∈VGDG(v)
　　Wiener指數(shù)主要體現(xiàn)為分子結(jié)構(gòu)的特征，屬于拓?fù)渲笖?shù)。在很多領(lǐng)域都有廣泛的應(yīng)