Research On Maximum Weighted Independent Sets On Large-scale Graphs

The independent set is a subset of the set of vertices in the graph,where there is no edge between the two vertices,and the maximum weighted independent set is the independent set with the largest sum of weights.The maximum weighted independent set problem studies how to search for the maximum weighted independent set from a given graph.The maximum weighted independent set can be used to solve the problem of resource allocation,which is important for scientific research and commercial applications.Existing methods have problems such as excessive weight loss,which leads to the fact that the sum of the maximum weighted independent set weights is not high.In addition,for the maximum weighted independent set problem on dynamic graphs,existing studies have not given a suitable solution.Aiming at the above problems,this paper studies the maximum weighted independent set problem on static graphs and dynamic graphs.The specific research content is as follows.First,a new maximum weighted independent set search method is proposed.This method continuously reduces the scale of the graph in an iterative manner,and obtains the largest weighted independent set in this process.In each step of the iterative process,on the one hand,the newly proposed equivalent reduction rules are used to select vertices that must belong to the result set,and on the other hand,heuristic rules based on loss values are used to select local optimal solutions.Secondly,for the calculation of the maximum weighted independent set of dynamic graphs,an approximate algorithm LSWTwo that supports efficient update is proposed.When the update operation occurs,the algorithm considers that the affected points are points within the range of 2.Therefore,by processing only the points in this range,the recalculation of the maximum weighted independent set can be avoided,and the efficiency of the update operation can be accelerated.The corresponding single add-delete point and single add-delete edge algorithm are proposed.Based on this,an optimized batch deletion point and batch edge addition algorithm is proposed,which reduces computational redundancy and improves the search speed.Finally,experimental tests are conducted based on multiple real data sets,and the reduction time,the number of reduced vertices,the search time and the sum of the weights of the maximum weighted independent set are used as indicators to verify the efficiency of the algorithm proposed in this paper.The experimental results show that the method proposed in this paper can efficiently search for the maximum weighted independent set on the static graph and the dynamic graph.