基于贪婪算法的最小（2,m）-连通控制集问题研究

发布时间：2024-12-20 23:09

　　连通控制集问题在计算机科学,运筹学等多个领域有广泛的应用.为了节约资源,图的连通控制集常作为无线传感器网络的虚拟骨干.而由于无线传感器网络中的传感器节点容易发生故障,需要建立一个容错的虚拟骨干来保持一定程度的冗余,因此研究k-连通m-折叠控制集问题是非常必要的.给定一个图G,正整数k和m.设C是顶点集V的一个顶点子集,如果由C诱导的子图k-连通,并且V\C中的每个顶点都与C中至少m个顶点相邻,则称C是图G的一个k-连通m-折叠控制集.本文研究2-连通图G上的最小2-连通m-折叠控制集问题,给出一个贪婪算法,并证明该算法的近似比是ln(Δ+m+2)+5,其中△是图G中顶点的最大度.

【文章页数】：33 页

【学位级别】：硕士

【文章目录】：
中文摘要
英文摘要
引言
第一章 预备知识
    1.1 图的基本概念
    1.2 图的连通控制集
第二章 (2,m)-连通控制集的贪婪算法
    2.1 势函数的构作
    2.2 势函数的性质
    2.3 贪婪算法
第三章 算法的理论分析
    3.1 相关引理
    3.2 近似比分析
结论
参考文献
致谢



本文编号：4018008