Local Search Algorithms For Solving Variant Problems Of Dominating Set

The minimum dominating set is a classic NP hard combinatorial optimization problem.The minimum k-dominating set problem and the minimum total dominating set problem are two important variation problems of minimum dominating set.The minimum k-dominating set and minimum total dominating set have important applications in many fields such as document processing,social network,distributed network design and AD hoc communication network.Therefore,the research on these two combinatorial optimization problems has important theoretical significance and application value.The algorithms to solve combinatorial optimization problems are mainly divided into precise algorithms and heuristic algorithms.The precise algorithm can find the optimal solution of the problem,but with the increase of the problem scale,the precise algorithm can not find the optimal solution in an acceptable time.The heuristic algorithm can find an optimal solution or approximate optimal solution in an acceptable time.Local search is a classical heuristic algorithm for solving combinatorial optimization problems.The main work of this paper is to design efficient local search algorithms for k-dominating set problem and total dominating set problem.For the minimum k-dominating set problem: this paper proposes a local search algorithm VSCC2 to solve the minimum k-dominating set problem.There are three key techniques in this algorithm: MKDS two-level configuration checking strategy,scoring mechanism based on vertex penalty and vertex selection strategy.The MKDS two-level configuration checking strategy is used to avoid circulation phenomenon during local search.The scoring mechanism based on vertex penalty helps the algorithm to select the appropriate vertex,thus it improves the search efficiency of the algorithm.By combining MKDS two-level configuration checking strategy and scoring mechanism based on the vertex penalty,this algorithm implements the vertex selection strategy to determine the appropriate vertex to add into or remove from the candidate solution.In order to verify the validity of this algorithm VSCC2,it is compared with the classical GRASP algorithm and the accurate solver CPLEX on the classical benchmark instances.Experimental results show that VSCC2 algorithm is very competitive in terms of solution quality and solution time.In this paper,local search algorithm LS_DTR based on dynamic scoring is proposed to solve the total dominating set problem.The key techniques of LS_DTR include dynamic scoring function,Ta CC2 strategy,balanced random walk strategy and vertex selection strategy.The dynamic scoring function can guide the search direction effectively.By combining Tabu strategy and two-level configuration checking(CC2)strategy,Ta CC2 strategy is proposed to reduce the circulation phenomenon during local search.In order to increase the diversity of local search,the algorithm LS_DTR implements a balanced random walk strategy.Based on dynamic scoring function,Ta CC2 strategy and balanced random walk strategy,vertex selection strategy is proposed.Vertex selection strategy is used to select vertices to be added into or removed from candidate solution.In the experimental section,LS_DTR is compared with the precise solver CPLEX and the best algorithms available.To further test the effectiveness of the algorithm,we not only test on the DIMACS instance,but also extend the test instance to the general graph and the unit disk graph.Experimental results show that LS_DTR has better performance than other algorithms.