学位论文 > 优秀研究生学位论文题录展示
网络中的超图嵌入问题
作 者: 王琦
导 师: 李国君
学 校: 山东大学
专 业: 运筹学与控制论
关键词: WDM 路由 通讯请求 阻塞度 判定问题 时序安排 超图 多项式时间归结 可行解 波长分配
分类号: O157.5
类 型: 博士论文
年 份: 2007年
下 载: 216次
引 用: 0次
阅 读: 论文下载
内容摘要
在全光网络中,波分复用(Wavelength Division Multiplexing)网络技术在现实的通信世界中扮演着基础和决定性的角色。若把网络看作一个图的模型,对于网络中的每一个通讯请求,如果每一个通讯请求恰好只有网络中的两个节点组成(一个源信号节点和一个接收信号节点),那么在图模型中需要选择一条路当作它的通讯频道来满足其通讯请求。而对于所有此类通讯请求,需要在图模型中选定一系列通路来实现网络中的通讯请求,这些通路就组成了这组通讯请求的一个路由。通常在实际的通讯网络中一个通讯请求含有网络中两个以上的节点,所以这种更普遍的情况是将这一系列通讯请求看作是图(或网络)中的一个超图,而其中每个通讯请求看作是此超图中的一条超边。为了实现这种通讯请求,对超图中每条超边需要确定一个路由算法来建立图(或网络)中一条虚拟通路或者说专用通路来连接此超边的每个节点,在确定这样一个路由算法中最重要的一点是使得图中的每条边上的最大阻塞度(congestion)最小,其中阻塞度为任意一条边上通过的通路的数量,此问题称作路由和波长(RWA)分配问题。如果将网络限定在一个环网络中,问题变为确定一个路由算法来实现超图在此环中的通讯请求,并且使得此环中任意一边上的最大阻塞度最小。此问题称作最小化超图嵌入圈的最大阻塞度(MCHEC)问题。此问题的结果在实际生活中应用广泛,例如在并行计算问题中,并行计算机的处理器可以代表是超图的所有顶点,其中需要互相传递信息的各组处理器看作是一条超边,MCHEC问题的最优解对每一组内所有处理器之间的通讯确定了一个路由算法使得计算机之间的最大阻塞度最小。本论文主要研究来源于WDM网络带宽分配问题的几个超图嵌入问题,对两类有较深应用价值的网络结构:树环网络和环圈网络,考虑了其超图嵌入问题;而后讨论了有关加权有向超图在网络中的嵌入问题,以及图论中有向图的几个问题,共分为五章。第一章主要介绍了WDM网络的一些相关的最优化问题,关键定义和相关结论,以及一些有向图问题的来源和相关结论。在第二章我们简化了MCHEC问题的算法,用新的方法证明了几个关键引理并且分别给出MCHETR(超图嵌入树环)问题和MCHERC(超图嵌入环圈)问题的PTAS算法。Ganley和Cohoon提出了MCHEC问题并且证明了此问题为NP-完备的。定理1 [51]MCHEC问题为NP-完备的。MCHEC问题存在一个PTAS算法[20]。在算法进行过程中我们将超边分为两部分来嵌入:Ri1,i2,…,ik和Ui1,i2,…,ik,对不同的u=|Ui1,i2…,ik|超边的嵌入又分两种情况来讨论。当超边的数目为一个小数目时,利用穷举的方法易证MCHEC问题的PTAS算法是存在的。定理2 [20]对任意的常数C>0,当超边的数目u≤C(log n)时,Ui1,i2,…,ik中的超边嵌入到圈中存在一个PTAS算法。特别地,对任一ε>0,一个(1+ε)近似比的近似结果可以在O(n*(C+1)/ε))时间内找到。应用线性放松和反随机方法来近似的解决超边为大数目时的MCHEC问题。可得如下定理。定理4 [20]当超边数目m足够大,且Copt≥cm(0<c≤1)时,MCHEC问题存在一个PTAS算法。结合定理2和定理4,应用解决字符串问题的方法[60]可证明下面的定理。定理5 [20]MCHEC问题存在一个PTAS算法。我们可以变换嵌入的对象,讨论两个相关问题:MCHETR(超图嵌入树环)问题和MCHERC(超图嵌入环圈)问题。应用MCHEC问题的算法,可以得出这两个相关问题的PTAS证明。从而可得如下定理。定理6 MCHETR问题存在一个PTAS算法。定理8 MCHERC问题存在一个PTAS算法。应用定理1的结论我们可以得到上述两个问题的NP-完备性证明。定理7 MCHETR问题为NP-完备的。定理9 MCHERC问题为NP完备的。在第三章我们首次提出了加权有向超图嵌入圈(WDHEC)问题。此问题是MCHEC问题的加权有向版本。类似于MCHEC问题的定义,WDHEC问题将一个加权有向超图的每条超边以一条加权有向路的形式嵌入到一个强连通有向圈中,并且使得最大阻塞度(圈中的任一弧上经过的加权有向路的权重之和)最小。WDHEC问题可以表达为一个整数线性规划的形式。然后结合PARTITION问题的判定问题和仅含有两个顶点的WDHEC问题的判定问题在多项式时间内的转换我们可以证明WDHEC问题的NP-完备性。定理10即使圈中仅含有两个顶点,WDHEC问题依然为NP-完备的。通过一个简单的贪婪算法我们可以在线性时间内得到WDHEC问题的一个近似比为2的近似解。定理11由贪婪算法得到的WDHEC问题最大阻塞度的近似值不超过最优解阻塞度的两倍。第四章主要介绍了强竞赛图的定义及相关性质,利用这些性质我们得到强竞赛图的一个新的强连通性质(见如下定理)。定理13在强竞赛图T中,如果顶点数不少于4个,则在T中存在两个不同的顶点{x,y},使得T-x和T-y均为强竞赛图。通过此性质我们可以得到Moon定理一个简洁的证明。Moon定理[64]T是有n个顶点的强竞赛图,n≥3,ν是T中的任意一个顶点,则对于任意的κ∈{3,4,…,n},在T中存在一个包含ν的k-圈。在第五章介绍了无向图的定向问题。很多人对于竞赛图和n部图的定向问题进行研究并且得到了一些有用的性质。利用这些性质我们提出了一类特殊图-split完全图的最小直径定向问题。一个split完全图S(m,n)由一个团和一个独立集构成,且团和独立集之间的边为完全的。令m,n分别为split完全图中团与独立集的顶点个数,f(S(m,n))表示S(m,n)所有定向中能够得到的最小直径。我们得到split完全图最小直径定向问题的结论。Claim:Case 1:当n≤(?)且m+n-2≥8,f(S(m,n))=2。Case 2:当n≥(?)且m+n-2≥8,问题仍然有待解决。我们期待对此定向问题更进一步的讨论,以及定向问题在更普通的图中的研究。本论文的创新点在于:1.用区别于邓和李的方法证明了MCHEC问题PTAS算法的几个关键引理,且首次提出超图嵌入环圈问题和超图嵌入环圈问题,并给出了这两个问题的NP-完备性证明和PTAS算法,解决了在两类有较深应用价值的网络结构(树环网络和环圈网络)中的多点通讯问题。2.首次提出加权有向MCHEC问题和加权有向MCHETR问题,得到加权有向MCHEC问题的NP-完备性证明,并且分别给出两个问题的2-近似算法。3.利用已知的强竞赛图的性质,得到强竞赛图一个新的强连通性质,并且应用此性质给出了Moon定理的一个简单的证明。4.提出了split完全图的定向问题,并且给出了一个最小直径定向的结果。
|
全文目录
中文部分 1-80 中文摘要 6-10 英文摘要 10-15 符号索引 15-16 第一章.前沿 16-23 §1.1 研究背景:基于波分复用技术的全光网络 16-17 §1.2 算法的一些关键定义 17-18 §1.3 WDM网络中的几个优化问题 18-20 §1.3.1 波长分配和路染色问题 19 §1.3.2 波长转换问题 19 §1.3.3 请求排序问题 19-20 §1.3.4 环负载问题 20 §1.4 一些优化问题的相关结论 20-21 §1.5 有向图的一些相关问题 21-23 §1.5.1 强连通图的强连通性 21-22 §1.5.2 最小直径定向问题 22-23 第二章.超图嵌入问题的一些PTAS算法 23-45 §2.1 引言 23-24 §2.2 MCHEC问题的来源以及一些相关的结论 24 §2.3 MCHEC问题的一个PTAS算法 24-35 §2.3.1 算法的思想 26-27 §2.3.2 嵌入下标在R_(i_1,i_2,…,i_r)中的超边 27-28 §2.3.3 完成下标在U_(i_1,i_2,…,i_r)中的超边的嵌入 28-35 §2.4 应用 35-44 §2.4.1 超图在树环中的嵌入问题 35-40 §2.4.2 超图在环圈中的嵌入问题 40-44 §2.5 总结 44-45 第三章.WDHEC问题的一个2-近似算法 45-56 §3.1 引言 45-46 §3.2 简介 46-48 §3.3 WDHEC问题的NP-完备性 48-51 §3.4 WDHEC问题的算法 51-52 §3.5 相关问题-WDHETR问题的算法 52-55 §3.6 总结 55-56 第四章.强竞赛图的强连通性 56-62 §4.1 引言 56 §4.2 简介 56 §4.3 强竞赛图的强连通性 56-60 §4.4 Moon定理的一个证明 60-61 §4.5 总结 61-62 第五章.Split完全图的最小直径定向问题 62-69 §5.1 引言 62-63 §5.2 简介 63-64 §5.3 split完全图的最小直径定向 64-68 §5.4 总结 68-69 参考文献 69-77 致谢 77-78 作者简介 78-79 学位论文评阅及答辩情况表 79-80 英文部分 80-171 Chinese abstract 86-90 English abstract 90-95 Notation index 95-96 Chapter 1. Introduction 96-106 §1.1 Motivation: The WDM networks 96-97 §1.2 Some key concepts of algorithms 97-99 §1.3 Some optimization problems of the WDM networks 99-102 §1.3.1 Wavelength assignment and path coloring 99-100 §1.3.2 Wavelength conversion 100-101 §1.3.3 Call scheduling 101 §1.3.4 Ring loading 101-102 §1.4 Related work of some optimization problems 102-103 §1.5 Some problems of graph theory 103-106 §1.5.1 Strong connectivity of strong tournaments 103-104 §1.5.2 The problem of minimal diameter orientation 104-106 Chapter 2. PTAS for hypergraph embedding problems 106-133 §2.1 Introduction 106-107 §2.2 Derivation of the MCHEC problem and related results 107-108 §2.3 A PTAS for the MCHEC problem 108-121 §2.3.1 Idea of the algorithm 110-112 §2.3.2 Embedding hyperedges with index in R_(i_1,i_2,...,i_r) 112-114 §2.3.3 Finish embedding hyperedges with index in U_(i_1,i_2,...,i_r) 114-121 §2.4 Application 121-132 §2.4.1 Embedding hypergraph in a trees of rings 121-127 §2.4.2 Embedding hypergraph in a rings cycle 127-132 §2.5 Conclusion 132-133 Chapter 3. A 2-approximation algorithm for the WDHEC problem 133-146 §3.1 Introduction 133-135 §3.2 Preliminaries 135-137 §3.3 NP-completeness of the WDHEC problem 137-140 §3.4 Algorithm for the WDHEC problem 140-142 §3.5 A related work-algorithm for the WDHETR problem 142-145 §3.6 Conclusion 145-146 Chapter 4. A new strong connectivity of strong tournaments 146-153 §4.1 Introduction 146 §4.2 Preliminaries 146-147 §4.3 Strong connectivity of strong tournaments 147-151 §4.4 Another proof of Moon Theorem 151-152 §4.5 Conclusion 152-153 Chapter 5. Minimal diameter orientation of special split graphs 153-161 §5.1 Introduction 153-154 §5.2 Preliminaries 154-156 §5.3 Minimal diameter orientation of complete split graphs 156-160 §5.4 Conclusion 160-161 Bibliography 161-169 Acknowledgements 169-170 Curriculum Vitae 170-171 学位论文评阅及答辩情况表 171
|
相似论文
- 宽带卫星网络中的TCP拥塞控制机制的研究,TN927.2
- 基于OLSR的Ad Hoc网络功率意识路由协议,TN929.5
- 高性能计算机I/O总线技术研究,TP336
- 基于测量的Internet链路延迟建模,TP393.4
- 基于LEACH的安全建簇无线传感器网络路由协议研究,TP212.9
- 车载CAN网络的网关设计方法研究,TP273
- 基于windows的计算机数字控制系统实时性的研究,TG659
- 基于地理位置的WSNs路由算法研究与改进,TN929.5
- 福建佛学院女众部的办学之路,B947
- 战场环境下Ad hoc网络路由协议性能分析,TN929.5
- 采用前方入路与后方入路治疗股骨头骨折的回顾性研究,R687.3
- 随机路由在无线传感器网络中的研究与应用,TN929.5
- 基于无线传感器网络的煤矿瓦斯监测系统的研究,TN929.5
- 基于无线传感器网络的农田环境监测系统路由协议的研究,TN915.04
- 应用Stoppa入路与髂腹股沟入路在骨盆前环骨折治疗中的比较性研究,R687.3
- 眶上锁孔入路椭圆形骨窗与长方形骨窗的比较,R779.6
- 青光眼视路改变应用磁共振成像评估的临床研究,R775
- 基于多层WSN结构的非均匀簇路由协议研究,TP212.9
- 大岛野路菊CcSOS1基因的克隆与表达分析,S682.11
- 基于节点智能交互的物联网数据处理研究,TP391.44
- 城市道路指路标志的微观仿真研究与实现,U491.52
中图分类: > 数理科学和化学 > 数学 > 代数、数论、组合理论 > 组合数学(组合学) > 图论
© 2012 www.xueweilunwen.com
|