本文關鍵詞： 通道布線 有向圈 色數 團　出處：《安徽理工大學》2017年碩士論文　論文類型：學位論文

【摘要】：通道布線問題是超大規(guī)模集成電路中的一個關鍵問題。雙層通道布線[1,2]的線網結構可以用垂直約束和水平約束進行描述,鑒于該特殊結構,能夠將圖論的思想運用到雙層通道布線中。本文在前人的基礎上,對垂直約束圖中含有圈的情況進行了討論,其中在含有一個圈的通道布線問題中,主要利用尋找并消除臨界網的方法給出布線的一個新的算法,該算法能夠得到軌道的一個下界。在含有多個圈時,主要從結點的兩類約束圖入手來研究布線算法,通過對垂直約束圖中含有有向圈的一類通道布線問題進行研究,設計出包含一對和兩對空結點情況下的布線算法,該方法能夠得到更好的軌道高度。并且對具體的布線過程進行了詳細的描述。Wiener指數[3]也是圖論的一個重要的應用,它在理論化學中運用十分廣泛。Wiener指數指一個圖中所有點對的距離之和,用如下式子表示:(?)Wiener指數主要體現為分子結構的特征,屬于拓撲指數。在很多領域都有廣泛的應用,諸如物理、化學、生物、通訊等。本文主要在已知一個連通圖的頂點數和色數或頂點數和團數情況下,討論所有點對的距離平方和的上下界問題,即(?)該指數建立在Wiener指數的基礎上,對分子結構特征具有一定的研究意義。
[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.
【學位授予單位】：安徽理工大學
【學位級別】：碩士
【學位授予年份】：2017
【分類號】：TN405;O157.5

【相似文獻】

相關期刊論文 前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è)學院學報;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];控制理論與應用;2004年03期

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

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

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

9 林曉霞;;粘貼運算下圖的Wiener多項式[J];廈門大學學報(自然科學版);2009年01期

10 陳婭紅;;樹變形下的Wiener指標[J];麗水學院學報;2009年02期

相關會議論文 前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 宋其江;陳翰馥;;帶內部噪聲的Wiener系統的辨識[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];中國自動化學會控制理論專業(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];中國自動化學會控制理論專業(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年

相關博士學位論文 前4條

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

2 徐守軍;圖的Wiener指標與Hosoya多項式[D];蘭州大學;2007年

3 周林成;Wiener非線性系統參數辨識方法研究[D];江南大學;2014年

4 任燕燕;基于智能計算的非線性系統辨識算法研究及其應用[D];華北電力大學;2014年

相關碩士學位論文 前10條

1 胡容維;圖的互補Wiener數與超-Wiener指標[D];新疆大學;2011年

2 牛志勇;關于圖的Wiener指標若干問題的研究[D];上海交通大學;2007年

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

4 趙雯雯;若干圖類的類Wiener指標研究[D];大連海事大學;2015年

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

6 蒿漢民;Hamilton圖的Wiener型指標[D];新疆大學;2015年

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

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

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

10 匡梅君;圖的Wiener-型指數與結構性質的研究[D];湖南師范大學;2015年

，

本文編號：1460723