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

An Efficient Algorithm For Maximum Weighted Independent Set on Dynamic Graph

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

The independent set is a subset of the vertex set in the graph,where there are no edges between the vertex set.The maximum weighted independent set is the independent set with the largest sum of weights.The maximum weighted independent set can be used to solve problems such as resource allocation and has an important role in scientific research and commercial applications.For the maximum weighted independent set problem on a dynamic graph,the existing research has not given a suitable solution.To solve this problem,this paper proposes an approximate algorithm LSWTwo that supports efficient update.When the update operation occurs,the algorithm takes into account the affected a point is a point within a distance of 2.Therefore,by processing only the points in this range,the re-search of the maximum weighted independent set can be avoided,and the efficiency of the update operation can be improved.Finally,compared on multiple real data sets,the experimental results verify the efficiency of the LSWTwo algorithm.