The minimum dominating set problem can be transformed into a series of decision problems-the k dominating set(k DS)problem and a hybrid tabu search and genetic(TSG)algorithm for solving the k DS problem is proposed.The algorithm combines a tabu search algorithm and a genetic algorithm.The ef-ficient neighborhood structure is used to ensure the efficiency of the algorithm,the tabu strategy is used to prevent the algorithm from falling into the local optimal trap,and the genetic algorithm framework is used to further enhance the evacuation of the algorithm.Compared with the existing algorithms for solving the minimum dominating set problem,the result of proposed algorithm outperforms the others.
关键词
最小支配集/NP难问题/禁忌遗传混合算法/k支配集
Key words
minimum dominating set/NP hard problem/hybrid tabu search and genetic algorithm/k-dom-inating set
维普
万方数据