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

论文摘要

随着因特网中应用的爆炸性增长与网络通讯技术的发展,无论在国防、财政和电源产业等传统领域,还是在新兴的可信计算和网络、云计算系统和下一代互联网等领域,网络的可靠性都得到越来越多的重视。如何在最小化占用网络资源的同时,通过网络的拓扑结构提高网络的可靠性,吸引了广大研究者的兴趣。本文集中研究了这个课题中的两个基础问题：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网络问题。

论文目录

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