图论在通道布线中的应用和Wiener指数问题研究

发布时间：2018-01-24 18:33

  本文关键词： 通道布线 有向圈 色数 团　出处：《安徽理工大学》2017年硕士论文　论文类型：学位论文

【摘要】：通道布线问题是超大规模集成电路中的一个关键问题。双层通道布线[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];四川工业学院学报;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状态滤波新方法[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];中国自动化学会控制理论专业委员会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];中国自动化学会控制理论专业委员会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