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

【摘要】：通道布線問(wèn)題是超大規(guī)模集成電路中的一個(gè)關(guān)鍵問(wèn)題。雙層通道布線[1,2]的線網(wǎng)結(jié)構(gòu)可以用垂直約束和水平約束進(jìn)行描述,鑒于該特殊結(jié)構(gòu),能夠?qū)D論的思想運(yùn)用到雙層通道布線中。本文在前人的基礎(chǔ)上,對(duì)垂直約束圖中含有圈的情況進(jìn)行了討論,其中在含有一個(gè)圈的通道布線問(wèn)題中,主要利用尋找并消除臨界網(wǎng)的方法給出布線的一個(gè)新的算法,該算法能夠得到軌道的一個(gè)下界。在含有多個(gè)圈時(shí),主要從結(jié)點(diǎn)的兩類約束圖入手來(lái)研究布線算法,通過(guò)對(duì)垂直約束圖中含有有向圈的一類通道布線問(wèn)題進(jìn)行研究,設(shè)計(jì)出包含一對(duì)和兩對(duì)空結(jié)點(diǎn)情況下的布線算法,該方法能夠得到更好的軌道高度。并且對(duì)具體的布線過(guò)程進(jìn)行了詳細(xì)的描述。Wiener指數(shù)[3]也是圖論的一個(gè)重要的應(yīng)用,它在理論化學(xué)中運(yùn)用十分廣泛。Wiener指數(shù)指一個(gè)圖中所有點(diǎn)對(duì)的距離之和,用如下式子表示:(?)Wiener指數(shù)主要體現(xiàn)為分子結(jié)構(gòu)的特征,屬于拓?fù)渲笖?shù)。在很多領(lǐng)域都有廣泛的應(yīng)用,諸如物理、化學(xué)、生物、通訊等。本文主要在已知一個(gè)連通圖的頂點(diǎn)數(shù)和色數(shù)或頂點(diǎn)數(shù)和團(tuán)數(shù)情況下,討論所有點(diǎn)對(duì)的距離平方和的上下界問(wèn)題,即(?)該指數(shù)建立在Wiener指數(shù)的基礎(chǔ)上,對(duì)分子結(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é)位級(jí)別】：碩士
【學(xué)位授予年份】：2017
【分類號(hào)】：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 鄧自立;時(shí)域Wiener狀態(tài)濾波新方法[J];控制理論與應(yīng)用;2004年03期

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

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

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

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

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

相關(guān)會(huì)議論文 前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];第二十四屆中國(guó)控制會(huì)議論文集（上冊(cè)）[C];2005年

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

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

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

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

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

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

9 ;Subspace Identification for Wiener Systems with General Nonlinearity[A];中國(guó)自動(dòng)化學(xué)會(huì)控制理論專業(yè)委員會(huì)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過(guò)程的產(chǎn)品退化建模與剩余壽命預(yù)測(cè)研究[D];國(guó)防科學(xué)技術(shù)大學(xué);2014年

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

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

4 任燕燕;基于智能計(jì)算的非線性系統(tǒng)辨識(shí)算法研究及其應(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)若干問(wèn)題的研究[D];上海交通大學(xué);2007年

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

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

5 胡文潔;給定直徑的樹(shù)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過(guò)程基于Wiener-Hopf分解的多層Monte Carlo算法實(shí)現(xiàn)中問(wèn)題的研究[D];復(fù)旦大學(xué);2014年

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

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

，

本文編號(hào)：1460723