The Research On Methods For Solving Several Dominating Set Optimization Problems

Dominating Set is considered to be among the most important conception in graph theory.The problem of Dominating Set and its variant,including Independent Dominating Set,Connected Dominating Set,and Total Dominating Set,etc,have not only be considered in science research,but also have varied applications in such fields as coding theory,image processing,numerical analysis,cryptography,information search,and communication network,city traffic route planning,etc.In the research,these problems are NP-hard in classical complexity theory,which means that it is impossible to design the algorithm finding the optimal solution with running reasonable time.In recent years,some heuristic algorithms and evolutionary algorithms arise,such as local search algorithms,genetic algorithms,etc.These algorithms have shown the efficiency for solving Dominating Set Problem.However,they have deficiencies for solving the complex optimization problems with characteristics of multiple constraints,multivariant and high-nonlinear,especially for the instances with large scaling.In this paper,we propose several algorithms for solving problem of Dominating Set and its variant,including Minimum Dominating Set Problems,Minimum Independent Dominating Set Problems,and Minimum Total Dominating Set Problems.In the algorithms,we introduce the local search method and the genetic algorithm.The experiment results show that these algorithms are efficient.The main research work and contributions are as follows.(1)It is important to solve the problems for Minimum Dominating Set(MDS).Recently,researchers have proposed several heuristic algorithms and get satisfied results to solve the MDS problems.However,these algorithms have pure efficiency encounting the problems with large scale.For this reason,we pay attention to research the algorithm for solving the MDS problems with large scale.By analyzing the large scale instances,we propose a fast algorithm to solve the MDS as FastMDS.FastMDS use several strategies to improve the efficiency,including the preprocess strategy with simplying the problem,the initialized strategy with low complexity,and the multi-value randomized selecting stratege.The experimental results show that the solving method for the problem of MDS we proposed has the higher efficiency than the classical heuristic algorithms.(2)The Minimum Total Dominating Set(MTDS)problem is a variant of the classical dominating set problem.In this paper,we propose a hybrid evolutionary algorithm combining local search and genetic algorithm to solve MTDS.A novel scoring heuristic is implemented to increase the searching effectiveness and get better solutions.For solving the MTDS problem,a population including several initial solutions is created firstly to make the algorithm search more regions.The local search phase improves the initial solutions by swapping vertices iteratively.The repair-based crossover operation creates new solutions to make the algorithm search more feasible regions.Experiments are carried out on the classical benchmark DIMACS,and the experimental results show that our algorithm performs much better than its competitor.(3)The Minimum Independent Dominating Set(MIDS)problem is a famous combinatorial optimization problem and is widely used in real-world domains.In this paper,we design a novel local search algorithm with tabu method and two phase removing strategies including double-checked removing strategy and random diversity removing strategy to solve the MIDS problem.The first removing strategy checks and then removes the second-level neighbourhood of the just removal vertex to break the limitation of the independence property.When the quality of candidate solution has not been improved for many iterations,the second removing strategy dynamically and greedily removes lots of vertices and then introduces the random walk into the adding vertices repair process,in order to escape from suboptimal search space.Experiments are carried out on two classical benchmarks named DIMACS and BHOSLIB,and the results show that our algorithm significantly outperforms the previous state-of-the-art heuristic algorithms for the MIDS problem.