学位论文 > 优秀研究生学位论文题录展示

基于不相交路径技术的可靠网络设计

作　者: 郭龙坤
导　师: 沈鸿
学　校: 中国科学技术大学
专　业: 计算机软件与理论
关键词: NP-完全性 近似算法 连通度 组合优化 Steiner网络 Min-Min路径 不相交路径 平面图
分类号: O157.5
类　型: 博士论文
年　份: 2011年
下　载: 72次
引　用: 0次
阅　读: 论文下载
 

内容摘要


随着因特网中应用的爆炸性增长与网络通讯技术的发展,无论在国防、财政和电源产业等传统领域,还是在新兴的可信计算和网络、云计算系统和下一代互联网等领域,网络的可靠性都得到越来越多的重视。如何在最小化占用网络资源的同时,通过网络的拓扑结构提高网络的可靠性,吸引了广大研究者的兴趣。本文集中研究了这个课题中的两个基础问题：Min-Min问题与Steiner网络问题。对于给定的带权图G=(V,E)以及源与目的结点s，t,Min-Min问题要求计算两条不相交的st-路径,使得其中较短的路径的权值最小。本文首先用一个反例指出了Bhatia等人关于无向图中边不相交Min-Min问题的NP-完全性证明是不成立的；然后基于一个从MAX-2SAT的归约,给出了该问题NP-完全性的一个正确证明。然后,本文研究了平面图中的Min-Min问题,证明了边不相交Min-Min问题在有向平面图中是NP-完全的。这些关于Min-Min问题的工作填补了目前理论上的一些空白。对于给定的带权图G=(V，E)、终端集S(?)V以及给定的正整数k,k-点/边连通的Steiner网络问题要求计算G的一个子图H,使得H权值最小且终端间的点/边连通度不小于k。本文首先总结了已有文献中Steiner网络问题的相关工作,然后分别设计了2,3-点连通的Steiner网络问题的近似比为2与8的近似算法。接着,通过对上述算法的扩展,设计了一个增加k-1边连通的Steiner网络的连通度,使之成为k-边连通Steiner网络的2-近似算法。最后本文给出一个反例,指出上述算法不能直接扩展到k点连通的Steiner网络问题。

全文目录


摘要  5-6
ABSTRACT  6-7
目录  7-9
第一章 绪论  9-19
  1.1 引言  9
  1.2 预备知识  9-12
    1.2.1 NP理论及近似算法的相关基本定义  9-11
    1.2.2 基本图论定义  11-12
  1.3 研究现状与相关工作  12-16
    1.3.1 Min-Min问题  12-14
    1.3.2 Steiner网络问题  14-16
  1.4 论文的内容与贡献  16-18
  1.5 小结  18-19
第二章 无向图中边不相交的Min-Min问题的NP-完全性  19-27
  2.1 Xu等人对Min-Min问题NP完全性的证明  19-20
  2.2 Bhatia等人的反例与替代的NP-完全性的证明  20-22
  2.3 对于Bhatia等人的证明的反例与及替代的正确证明  22-25
  2.4 小结  25-27
第三章 有向平面图中边不相交Min-Min问题的NP-完全性  27-34
  3.1 有向图中边不相交的Min-Min问题的NP-完全性  27-29
  3.2 有向平面图中边不相交的Min-Min问题的NP-完全性  29-32
  3.3 小结  32-34
第四章 Steiner网络中的高效近似算法综述  34-40
  4.1 最小生成子图问题  34-36
    4.1.1 κ-边连通的最小生成子图问题  34-35
    4.1.2 2,3-点连通的最小生成子图问题  35-36
  4.2 Steiner网络问题  36-39
    4.2.1 边连通的广义Steiner网络问题  36-38
    4.2.2 点连通的广义Steiner网络问题  38-39
  4.3 小结  39-40
第五章 2-点连通的Steiner网络问题  40-58
  5.1 一个简单的近似算法  40-41
  5.2 改进的近似算法  41-46
  5.3 近似比证明  46-54
    5.3.1 单源2点连通最小Steiner网络的分解  46-50
    5.3.2 欧拉回路的构造  50-54
  5.4 扩展算法5.1到2边连通的最小Steiner问题  54-57
  5.5 小结  57-58
第六章 3-点连通的Steiner网络  58-70
  6.1 近似算法  58-60
  6.2 近似比证明  60-63
  6.3 定理6.3的证明  63-68
  6.4 小结  68-70
第七章 κ-连通的Steiner网络  70-75
  7.1 κ-边连通的Steiner网络  70-71
  7.2 引理7.1的证明  71-73
  7.3 κ-点连通的Steiner网络  73-74
  7.4 小结  74-75
第八章 结论和展望  75-77
  8.1 结论  75-76
  8.2 展望  76-77
参考文献  77-83
致谢  83-84
在读期间发表的学术论文与取得的其他研究成果  84
  己发表论文  84
  返修中论文  84
  投稿中论文  84

相似论文

  1. 变邻域搜索算法研究及在组合优化中的应用,TP301.6
  2. 基于Copula风险控制的贷款组合优化模型研究,F224
  3. 连续竞争反应装置的效益优化方法与应用研究,TQ015
  4. 基于下偏度最小化贷款组合优化模型,F224
  5. 基于违约相关性的集中度风险控制方法研究,F830.5
  6. 高速公路融资结构优化研究,F540.58
  7. 蚁群优化算法及其应用研究,TP301.6
  8. 证券市场风险测量与修正,F832.51
  9. 乘积图的控制数与限制边连通度,O157.5
  10. 非线性无约束共轭梯度法,O224
  11. 几种常用的互连网络的超边连通容错度,O157.5
  12. 变电站经济运行与无功电压优化控制的研究,TM63
  13. 混合算法在物流运输问题中的研究和应用,TP301.6
  14. 求解组合优化问题的混合蛙跳算法的研究,TP301.6
  15. 解最小生成树问题的新的遗传算法,TP301.6
  16. 基于SV和Copula的投资组合风险度量及最优策略选择,F830.59
  17. 期货投资基金与资产组合效率优化研究,F224
  18. 不确定理论在金融风险管理领域中的应用,F830.91
  19. 基于蚁群算法的投资组合优化研究,F830.9
  20. 不确定优势理论及其应用,O211.6
  21. 有服务等级约束的平行机排序问题,O223

中图分类: > 数理科学和化学 > 数学 > 代数、数论、组合理论 > 组合数学（组合学） > 图论
© 2012 www.xueweilunwen.com