大规模图顶点覆盖的增量算法研究

发布时间：2022-01-27 12:38

　　顶点覆盖问题在图论中是一个经典的组合优化问题,并且在实际问题中有非常广泛的应用。针对大规模图顶点数目增加、边数目增加和顶点与边数目均增加3种动态过程,设计了能够在原极小顶点覆盖集合的基础上更新增量后图的极小顶点覆盖集合的算法。提出的算法考虑了图结构中顶点与边的关系,并采用邻接矩阵的方法对其进行存储,在图结构发生增量变化后,在原极小点覆盖集合的基础上添加或者删除若干顶点来更新增量后的极小顶点覆盖集合。实验结果验证了算法的准确性和高效性。 

【文章来源】：北京信息科技大学学报(自然科学版). 2020,35(05)

【文章页数】：6 页

【部分图文】：

边增量变化实例

尤攵サ?vp，考虑到需要在原顶点覆盖集合中删除不必要的顶点，只需证明删除的顶点是冗余的。因为vi+1与vp相邻接，并且?v"p∈V(vp)且v"p∈N0，那么所有和vp相邻接的并且属于原极小顶点覆盖集合N0的顶点即为v"p，而由题意，与v"p相连的若干个顶点都属于原N0，即对于?e∈E(v"p)，都有e被点覆盖集合N0中的顶点所覆盖，那么此时v"p是可以删去的，即v"p为冗余的得证，否则顶点v"p不能被删去。例1如图1所示，已知图G=＜V，E＞，且它的其中一个极小顶点覆盖集合为N0={v1，v4，v5}，如果新加入顶点为vi+1，利用上述定理求解更新后的极小顶点覆盖集合Nnew。由图可以看出，新加入的顶点vi+1与非顶点覆盖集合N0中的元素v2、v5相邻接，求解步骤如下:第一步先在原点覆盖集合N0中分别加入顶点v2、v5;第二步分别判断与v2、v5相连的原N0中的顶点中是否存在冗余的顶点。对于和v2相邻接的顶点有v1、v3，在比较过程中优先删去N0中度数较少的顶点。对于v1，与v1相连的所有的顶点是v2、v3，它们都属于N0中的顶点，根据定理2，此时v1可以删去。对于v3，与v3相连的所有的顶点为v1、v2、v4、v5，它们都属于N0中的顶点，而删去v1后，v3便不能再被删去。对于v4，与v4相连的所有的顶点为v3、v5，它们都属于N0中的顶点，因此根据定理2可以删去顶点v4。则

【参考文献】：
期刊论文
[1]一种增量式约简方法求解最小顶点覆盖问题[J]. 占善华,谢小军.  计算机应用研究. 2018(12)
[2]求解最小点覆盖问题实例的计算成本的一种度量方法[J]. 王丽丽,崔晋川.  数学的实践与认识. 2017(23)
[3]增量网络监测点的增量选取算法[J]. 丁三军,陶兴宇,石祥超,徐蕾.  计算机应用. 2015(12)
[4]基于最短路算法的最小点覆盖问题[J]. 寇磊,崔笑川,陈京荣.  兰州交通大学学报. 2015(04)
[5]广义Petersen图的最小点覆盖集[J]. 郑文萍,郭炳,杨贵.  山西师范大学学报(自然科学版). 2014(01)
[6]图的最小顶点覆盖的粘贴DNA计算模型[J]. 聂晓艳,耿俊,汤建钢.  首都师范大学学报(自然科学版). 2013(01)
[7]一种求解平面图的最小顶点覆盖算法[J]. 吴春,朱国魂,谢玉忠,林宏.  计算机系统应用. 2010(09)
[8]最小顶点覆盖问题的DNA分子算法[J]. 高琳,许进.  系统工程与电子技术. 2004(04)

硕士论文
[1]分布式系统日志数据采集关键技术研究与实现[D]. 陶兴宇.沈阳航空航天大学 2016



本文编号：3612504