Research On The Application Of Message Passing Algorithm For Dominating Set Problem

The minimum dominating set(MDS)problem is an important problem in graph theory,and it has a wide range of applications in network resource allocation.The construction of urban transportation network and communication network,the location of logistics network center,the location of connectivity facilities,and the setting of adaptive network can all be attributed to MDS problems.The solution of this problem has important theoretical guiding significance for the research of graph coloring,maximum matching,maximum independent set,minimum vertex cover,maximum set cover and other problems.However,this problem is a classic NP-hard problem.When P?NP,there is no polynomial time algorithm to solve this problem.At present,the algorithm research on this problem mainly focuses on two aspects: precise algorithm and approximate algorithm,accurate algorithms have higher solving accuracy,but the running time of the algorithm is longer;the running time of approximate algorithms is shorter,and it is usually impossible to obtain the exact solution of the problem.In fact,a large number of practical problems do not have high requirements on the accuracy of the solution,and only need the accuracy of the solution to reach a certain degree of approximation,which proves the wide application of approximation algorithms.Heuristic method is an effective strategy of the approximate algorithm.It has the characteristic of solving complex problems in a reasonable time.The heuristic algorithms commonly used to solve MDS problems include: genetic algorithm,ant colony algorithm,tabu search algorithm,etc.A common feature of this type of algorithm is that it is easy to fall into a local optimum.The belief propagation algorithm is a message passing algorithm based on factor graphs.When the algorithm converges,it can give the marginal probability of the value of the variable nodes in the factor graph.A large number of research results show that this algorithm can be used to effectively solve combinatorial optimization problems.Therefore,this article explores the use of belief propagation algorithm to solve MDS problems.Specifically,there are mainly the following two aspects of research work:(1)Mapping the minimum dominating set problem to a factor graph model.Constructing a linear programming equation based on the factor graph model,constructing the potential function of the belief propagation algorithm according to the objective function and constraint equation of the linear programming equation.(2)Designing an belief propagation algorithm for solving the minimum dominating set problem.When the algorithm converges,it can obtain the edge probability value of each node.The edge probability is used to determine the minimum dominating set node with high probability,and numerical experiments are performed on the randomly generated undirected graph.The results show that the method is effective.(3)Designing a communication base station site selection system based on belief propagation algorithms.Providing realistic application scenarios for the minimum dominating set problem and helps for the existing communications industry.