The Algorithm For Maximum Weighted Independent Sets On Weighted Dynamic Grapg

The vertices in an independent set are not connected to each other.When the vertices in the graph have weights,The maximum sum of vertex weights in the independent set is the maximum weighted independent set.This problem plays an important role in solving practical problems,such as the problem of network interference in wireless network scheduling.According to whether the graph being processed is a dynamic graph or not,there are two kinds of algorithms,which are static graph based method and dynamic graph based method respectively.In solving static graphs,the sum of weights of weighted independent sets obtained by existing methods is low.When the weights of the vertices on the dynamic graph change,only the method based on the static graph can be used to recalculate the whole graph at present,which is inefficient.Aiming at the problems of the existing methods,this paper proposes a new greedy strategy for solving static graphs.Aiming at the problem of weight updating on dynamic graph,a corresponding efficient processing strategy is proposed.The specific research contents are as follows:A new greedy strategy is proposed for solving static graphs.Based on the concept of loss value,the vertex with the smallest loss value and the largest loss value is found,and the vertex local optimal selection is carried out by combining the distance between vertices.In view of the weight changes of a single vertex,a basic algorithm is firstly proposed.The basics algorithm directly adds the difference of weight changes into the weight sum of the maximum weighted independent set.But the Basics algorithm ignores the possible existence of a maximum weighted independent set with a larger sum of weights.To solve this problem,this paper proposes the optimization algorithm Up Wei algorithm,which decomposes the weight change problem into five cases,and puts forward corresponding strategies for each case.When the weights of several vertices change at the same time,the Up Wei algorithm is used to deal with the vertices in turn.To solve this problem,this paper proposes Upb Inc algorithm and Upb Dec algorithm.The Upb Inc algorithm assigns priority to vertices according to the difference of vertex weight changes,and determines the processing sequence by priority.The Upb Inc algorithm determines whether the influence range of vertices overlaps by the distance between vertices,and merges the overlapped parts.Upb Inc algorithm and Upb Dec algorithm avoid redundant calculation and improve the computational efficiency of batch vertex weight update.Finally,experiments are carried out on 23 real data sets.In this paper,the efficiency is verified by searching time and summation of weights of the maximum weighted independent set.Experimental results show that the proposed method can quickly solve the approximate maximum weighted independent set.It can support efficient solution on dynamic graph,and the sum of weights of the maximum weighted independent set obtained is higher.