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