Research On The Heuristic Algorithms For The Minimum Dominating Set Problem Of Graph

The minimum dominating set problem is a classic NP-hard problem in graph theory.The solution to the minimum dominating set problem is to find a minimum subset of the vertex set of the graph,where any vertex not in the selected subset is adjacent to at least one vertex in the subset.Minimum Dominating set has a wide range of applications,such as social network information mining,finding key genes in bioinformatics,and setting up communication network base stations.This paper designs a heuristic algorithm for solving the minimum dominating set problem through the research of related theories and algorithms,that is,the two-stage local search(TSLS)algorithm.The algorithm uses a mixed local search strategy which divides the local search into two stages.In the first stage,rough optimization is performed on the basis of the initial feasible solution,and then local fine optimization is performed on the results of the first stage.At the same time,the algorithm also improves the Two-goal search algorithm,and the improved algorithm is used in the first stage of the Two-goal search,and the effect is better.The algorithm also added the improved tabu strategy,and the experiment also proved that the strategy is effective.Then,the TSLS algorithm is also evaluated on seven datasets,including four standard datasets and three large-scale datasets.The result is that TSLS achieves the best results on all seven datasets.The TSLS algorithm is obviously better than RLSo and Sc Bppw,and compared with state-of-the-art algorithm Fast DS,it also has certain advantages.Finally,apply the dominating set of the graph to specific problems,that is,designing a social network influence maximization algorithm which is based on the dominating set—Dom IM algorithm.Based on the dominating set,the algorithm utilizes the uncorrelated degree information of vertices and adopts a local search strategy of exchanging vertices.It is also compared with other algorithms through experiments,and the results show that the algorithm has achieved the best results on all the graphs used in the experiment.Through the further analysis of the experimental results,it shows the high efficiency of the algorithm.