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

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