本文關(guān)鍵詞： 通道布線 有向圈 色數(shù) 團(tuán)　出處：《安徽理工大學(xué)》2017年碩士論文　論文類型：學(xué)位論文

【摘要】：通道布線問題是超大規(guī)模集成電路中的一個關(guān)鍵問題。雙層通道布線[1,2]的線網(wǎng)結(jié)構(gòu)可以用垂直約束和水平約束進(jìn)行描述,鑒于該特殊結(jié)構(gòu),能夠?qū)D論的思想運(yùn)用到雙層通道布線中。本文在前人的基礎(chǔ)上,對垂直約束圖中含有圈的情況進(jìn)行了討論,其中在含有一個圈的通道布線問題中,主要利用尋找并消除臨界網(wǎng)的方法給出布線的一個新的算法,該算法能夠得到軌道的一個下界。在含有多個圈時,主要從結(jié)點(diǎn)的兩類約束圖入手來研究布線算法,通過對垂直約束圖中含有有向圈的一類通道布線問題進(jìn)行研究,設(shè)計(jì)出包含一對和兩對空結(jié)點(diǎn)情況下的布線算法,該方法能夠得到更好的軌道高度。并且對具體的布線過程進(jìn)行了詳細(xì)的描述。Wiener指數(shù)[3]也是圖論的一個重要的應(yīng)用,它在理論化學(xué)中運(yùn)用十分廣泛。Wiener指數(shù)指一個圖中所有點(diǎn)對的距離之和,用如下式子表示:(?)Wiener指數(shù)主要體現(xiàn)為分子結(jié)構(gòu)的特征,屬于拓?fù)渲笖?shù)。在很多領(lǐng)域都有廣泛的應(yīng)用,諸如物理、化學(xué)、生物、通訊等。本文主要在已知一個連通圖的頂點(diǎn)數(shù)和色數(shù)或頂點(diǎn)數(shù)和團(tuán)數(shù)情況下,討論所有點(diǎn)對的距離平方和的上下界問題,即(?)該指數(shù)建立在Wiener指數(shù)的基礎(chǔ)上,對分子結(jié)構(gòu)特征具有一定的研究意義。
[Abstract]:Channel routing is a key problem in VLSI. Double-layer Channel routing. [The network structure can be described by vertical and horizontal constraints. In view of this special structure, the idea of graph theory can be applied to double-layer channel routing. In this paper, we discuss the case of the perpendicular constraint graph with cycles. In the problem of channel routing with one cycle, we mainly use the method of searching and eliminating the critical network to give a new algorithm for routing. This algorithm can obtain a lower bound of orbit. When there are multiple cycles, the routing algorithm is mainly studied from two kinds of constraint graphs of nodes. By studying a class of channel routing problems with directed cycles in vertical constraint graphs, a routing algorithm with a pair of empty nodes and two pairs of empty nodes is designed. This method can get better orbital height. And the detailed routing process is described in detail .Wiener exponent. [3] is also an important application of graph theory. It is widely used in theoretical chemistry. Wiener index refers to the sum of the distances of all points in a graph. Wiener index is the characteristic of molecular structure and belongs to topological index. It is widely used in many fields, such as physics, chemistry and biology. In this paper, we discuss the upper and lower bounds of the sum of distance square of all point pairs when we know the number of vertices and chromatic numbers or the number of vertices and groups of a connected graph. The index is based on the Wiener index and has a certain significance for the study of molecular structural characteristics.
【學(xué)位授予單位】：安徽理工大學(xué)
【學(xué)位級別】：碩士
【學(xué)位授予年份】：2017
【分類號】：TN405;O157.5

【相似文獻(xiàn)】

相關(guān)期刊論文 前10條

1 ;Exact Rates of Convergence of Functional Limit Theorems for Csorgo-Revesz Increments of a Wiener Process[J];Acta Mathematica Sinica(English Series);2002年04期

2 陳廣貴,房艮孫;多元Paley-Wiener空間的離散性(英文)[J];四川工業(yè)學(xué)院學(xué)報(bào);2003年S2期

3 ;Receiver Function Estimated by Wiener Filtering[J];Earthquake Research in China;2003年04期

4 ;Reforming of Wiener Index[J];Wuhan University Journal of Natural Sciences;2004年01期

5 鄧自立;時域Wiener狀態(tài)濾波新方法[J];控制理論與應(yīng)用;2004年03期

6 馮惠英;;具有最小的Wiener-Hosoya index的樹[J];南平師專學(xué)報(bào);2006年02期

7 湯自凱;;直鏈苯撐圖的一般Wiener指數(shù)[J];湖南文理學(xué)院學(xué)報(bào)(自然科學(xué)版);2007年02期

8 馮惠英;錢建國;;具有最大Wiener-Hosoya指標(biāo)的樹[J];漳州師范學(xué)院學(xué)報(bào)(自然科學(xué)版);2007年04期

9 林曉霞;;粘貼運(yùn)算下圖的Wiener多項(xiàng)式[J];廈門大學(xué)學(xué)報(bào)(自然科學(xué)版);2009年01期

10 陳婭紅;;樹變形下的Wiener指標(biāo)[J];麗水學(xué)院學(xué)報(bào);2009年02期

相關(guān)會議論文 前10條

1 M.Mansouri;H.Tolouei;M.Aliyari Shoorehdeli;;Identification of Hammerstein-Wiener ARMAX Systems Using Extended Kalman Filter[A];Proceedings of the 2011 Chinese Control and Decision Conference（CCDC）[C];2011年

2 ;FIR Reduced Rank Wiener Filter[A];第二十四屆中國控制會議論文集（上冊）[C];2005年

3 ;Recursive Identification of Wiener Systems with Nonparametric Nonlinearity[A];第二十四屆中國控制會議論文集（上冊）[C];2005年

4 宋其江;陳翰馥;;帶內(nèi)部噪聲的Wiener系統(tǒng)的辨識[A];第二十七屆中國控制會議論文集[C];2008年

5 ;Recursive Identification of Wiener Systems with General Inputs[A];第二十七屆中國控制會議論文集[C];2008年

6 ;PSO and RBF Network-Based Wiener Model and Its Application to System Identification[A];第24屆中國控制與決策會議論文集[C];2012年

7 ;Recursive Identification for Wiener-Hammerstein System[A];中國自動化學(xué)會控制理論專業(yè)委員會C卷[C];2011年

8 ;Identification of Wiener Models with Binary-Valued Output Observations[A];第25屆中國控制會議論文集（上冊）[C];2006年

9 ;Subspace Identification for Wiener Systems with General Nonlinearity[A];中國自動化學(xué)會控制理論專業(yè)委員會A卷[C];2011年

10 Xiaoying Deng;Yong Luo;;Random Noise Attenuation Based on Support Vector Regression and Adaptive Wiener Filtering[A];proceedings of 2010 3rd International Conference on Computer and Electrical Engineering (ICCEE 2010 no.1)[C];2012年

相關(guān)博士學(xué)位論文 前4條

1 王小林;基于非線性Wiener過程的產(chǎn)品退化建模與剩余壽命預(yù)測研究[D];國防科學(xué)技術(shù)大學(xué);2014年

2 徐守軍;圖的Wiener指標(biāo)與Hosoya多項(xiàng)式[D];蘭州大學(xué);2007年

3 周林成;Wiener非線性系統(tǒng)參數(shù)辨識方法研究[D];江南大學(xué);2014年

4 任燕燕;基于智能計(jì)算的非線性系統(tǒng)辨識算法研究及其應(yīng)用[D];華北電力大學(xué);2014年

相關(guān)碩士學(xué)位論文 前10條

1 胡容維;圖的互補(bǔ)Wiener數(shù)與超-Wiener指標(biāo)[D];新疆大學(xué);2011年

2 牛志勇;關(guān)于圖的Wiener指標(biāo)若干問題的研究[D];上海交通大學(xué);2007年

3 宋夢華;樹的Wiener指標(biāo)的若干極值問題和二部Wiener向量[D];集美大學(xué);2015年

4 趙雯雯;若干圖類的類Wiener指標(biāo)研究[D];大連海事大學(xué);2015年

5 胡文潔;給定直徑的樹Wiener指數(shù)研究[D];上海交通大學(xué);2015年

6 蒿漢民;Hamilton圖的Wiener型指標(biāo)[D];新疆大學(xué);2015年

7 阿米妮姑麗·吾馬爾;單圈圖的反Randi鋫指標(biāo)及Mycielskian圖的Wiener與Zagreb指標(biāo)[D];新疆大學(xué);2015年

8 余敏華;β族Lévy過程基于Wiener-Hopf分解的多層Monte Carlo算法實(shí)現(xiàn)中問題的研究[D];復(fù)旦大學(xué);2014年

9 馬晶;給定直徑d的單圈圖的Wiener極化指數(shù)的極值問題[D];南開大學(xué);2015年

10 匡梅君;圖的Wiener-型指數(shù)與結(jié)構(gòu)性質(zhì)的研究[D];湖南師范大學(xué);2015年

，

本文編號：1460723