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

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

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