一种高效的动态图最大加权独立集求解算法

• 作者: 祁才云 周军锋 杜明
• 来源期刊: 新一代信息技术
• 关键词: 最大加权独立集 动态图 近似算法
• 年，卷（期）: 2021,（7）
• 所属期刊栏目: 科技论文
• 页码范围: 1-8
• 页数: 8页
• 分类号: TP391
• 语种: 中文
• DOI: 10.3969/j.issn.2096-6091.2021.07.001

摘要

独立集是图中顶点集的子集,该子集中的顶点之间不存在边.最大加权独立集是权值总和最大的独立集.最大加权独立集可以用来解决资源分配等问题,对于科学研究、商业应用等有重要作用.对于动态图上的最大加权独立集问题,现有研究并未给出合适的解决方案,本文针对此问题,提出支持高效更新的近似算法LSWTwo,当更新操作发生时,该算法考虑到受影响的点是距离为2范围内的点,因此,通过只处理该范围的点,可避免对最大加权独立集的重新搜索,提升更新操作的效率.最后,在多个真实数据集上进行比较,实验结果验证了LSWTwo算法的高效性.