s-路径顶点覆盖问题的算法研究

论文摘要

在计算机网络中,每一个网络节点都执行着信息生成、路由选择、信息转发、信息接收等多项任务。但是,其中一些节点还负责执行其它的附加任务,例如,收集和分析网络中信息瘫痪的资料、丢弃来自网络的攻击信息等,称这些执行附加任务的节点为网络观察员。如果将网络中的所有节点都设置成观察员节点,不仅严重浪费网络资源,还会增加建设网络的成本。所以需要解决的问题是求出该网络的一个规模最小的网络观察员节点子集,使得每一条通过网络中s（s≥2）个节点传播的信息至少被该节点子集中的一个节点观察到。加之受无线传感网络安全通信问题的启发,人们提出了s-路径顶点覆盖这一问题。此外,无线传感网络中最优链路构造、各种网络环境中监控设备的安置等问题都可以看做是s-路径顶点覆盖问题在实际中的应用。s-路径顶点覆盖问题是指：给定一个无向图和一个正整数s,从该图中找出一个规模最小的顶点子集,使得该图中每条长度为s-1的路径至少包含了该顶点子集中的一个顶点。该问题已经被证明是NP-完全的。本文主要利用参数化计算技术设计求解s-路径顶点覆盖问题的精确算法,所做工作有：1给出一个解决树上的s-路径顶点覆盖问题的最优算法。2利用深度有界搜索树方法设计解决3-路径顶点覆盖问题的精确算法,经过一系列的改进,最终得到时间复杂度为O*(2.3028勺的算法。3利用深度有界搜索树方法设计解决4-路径顶点覆盖问题的精确算法,经过一系列的改进,最终得到时间复杂度为O*(3.0122勺的算法。

论文目录

• 摘要
• ABSTRACT
• 第一章 绪论
• 1.1 应用背景
• 1.2 研究现状
• 1.3 参数化算法
• 1.3.1 深度有界搜索树
• 1.4 文章组织结构
• 第二章 s-路径顶点覆盖问题的研究
• 2.1 s-路径顶点覆盖问题
• 2.1.1 s-路径顶点覆盖问题的复杂性
• 2.2 树上的s-路径顶点覆盖问题的最优算法
• 2.3 本章小结
• 第三章 3-路径顶点覆盖问题的算法研究
• 3.1 3-路径顶点覆盖
• 3.2 3-路径顶点覆盖问题的一个最优算法
• 3.3 3-路径顶点覆盖问题算法的改进
• 3.3.1 算法的第一次改进
• 3.3.2 算法的第二次改进
• 3.3.3 算法的第三次改进
• 3.3.4 算法的第四次改进
• 3.3.5 算法的第五次改进
• 3.4 本章小结
• 第四章 4-路径顶点覆盖问题的算法研究
• 4.1 4-路径顶点覆盖
• 4.2 4-路径顶点覆盖问题的一个最优算法
• 4.3 4-路径顶点覆盖问题算法的改进
• 4.3.1 算法的第一次改进
• 4.3.2 算法的第二次改进
• 4.3.3 算法的第三次改进
• 4.3.4 算法的第四次改进
• 4.3.5 算法的第五次改进
• 4.4 本章小结
• 第五章 总结与展望
• 5.1 工作总结
• 5.2 工作展望
• 参考文献
• 致谢
• 攻读学位期间发表的学术论文目录
• 学位论文评阅及答辩情况表