Models and Algorithm for Stochastic Minimum Weight Dominating Set Problem
The minimum weight dominating set problem is a classical optimization problem in graph theory,which has many real applications.In real life,there always exist various kinds of uncertainty,thus it is necessary to take uncertainties into account when studying dominating set.In this paper,the stochastic minimum weight dominating set problem is studied.We propose the concepts of α-minimum weight dominating set and the most minimum weight dominating set.According to the two decision criteria,different types of decision model are formulated.We produce a hybrid intelligent algorithm integrating stochastic simulation with genetic algorithm to solve the proposed models.Finally,numerical experiments are given to illustrate the effectiveness of the algorithm.
dominating set stochastic programming stochastic simulation genetic algorithm
Yue Zhou Yaodong Ni
School of Information Technology and Management University of International Business and Economics,Beijing 100029,China
国内会议
开封
英文
219-227
2012-05-25（万方平台首次上网日期，不代表论文的发表时间）