Research On Incremental Algorithm For Solving Large-scale Graph Vertex Coverage

The Minimal vertex cover problem(MVCP)is a classical combinatorial optimization problem in graph theory,and it is widely used in practical problems.Three dynamic processes of increasing the number of vertices,increasing the number of edges,and increasing the number of vertexes and edges simultaneously in large-scale graphs,and the algorithm that can update the minimum vertex coverage of the post-incremental graph on the basis of the original minimum vertex cover set is designed.The proposed algorithms consider the relationship between vertices and edges in the graph,and employs the adjacency matrix to store it.After the incremental change of the graph structure,the proposed algorithm add or delete several vertices on the basis of the original minimum point coverage to update the incremental minimum vertex cover.Experimental results verify the accuracy and efficiency of the algorithm.The weighted graph vertex cover(MWVCP)problem is an extension of the general graph vertex cover problem.Assign specific weights to the vertices of the general graph.These weights have specific practical meanings in reality,such as representing cost,expense,distance,etc.Solving the vertex cover of the weighted graph can be combined with the solving idea of the general graph.According to the solution idea of the general graph,the vertex cover is updated and iterated first,and then the obtained set is reduced by the idea of branch reduction.Experiments have proved that the weight of the vertices is ignored when the elements in the vertex coverage are updated and iterated in the early stage,and the vertices with larger weights will be effectively replaced when the pruning reduction is performed in the later stage.