The Minimum Weight Dominating Set Problem under Hybrid Uncertain Environments


Article Preview

The minimum weight dominating set problem (MWDSP) has been a popular research topic in recent years. The weights of vertexes may be considered as cost, time, or opponent’s payoff, which are uncertain in most cases. This paper discusses MWDSP under hybrid uncertain environments where the weights of vertexes are random fuzzy variables. First, random fuzzy theory is introduced to describe these hybrid uncertain variables. Then we propose three decision models based on three different decision criteria to solve MWDSP under hybrid uncertain environments. To solve the proposed models, we present a hybrid intelligent algorithm where random fuzzy simulation and genetic algorithm are embedded. Numerical experiments are performed in the last to show the robustness and effectiveness of the presented hybrid intelligent algorithm.



Edited by:

Li Qiang




C. Y. Wang et al., "The Minimum Weight Dominating Set Problem under Hybrid Uncertain Environments", Applied Mechanics and Materials, Vol. 624, pp. 545-548, 2014

Online since:

August 2014




* - Corresponding Author

[1] M. Farber and J. M. Keil, Domination in permutation graphs, Springer-Verlag, vol. 6, 309-321, (1985).

[2] S. Guha and S. Khuller, Approximation algorithms for connected dominating sets, In Proceedings of the 4th ann. European Symp. On Alg. LNCS1136, 179-193, (1996).


[3] Y.P. Chen and A.L. Liestman, Approximating Minimum Size Weakly-Connected Dominating Sets for Clustering Mobile Ad-Hoc Networks, In Proceedings of 3rd ACM International Symposium on Mobile Ad-Hoc Networking and Computing. ACM press, 165-172, (2002).


[4] Y.D. Ni, Stochastic minimum weight vertex cover problem, proceeding of the 5th International Conference on Information and Management Sciences: 358-364, (2006).

[5] Y.D. Ni, Fuzzy Minimum Weight Edge Covering Problem, Applied Mathematical Modeling, vol. 32, No. 7, 1327-1337, (2008).


[6] B. Liu, Theory and Practice of Uncertain Programming, Physica-Verlag, Heidelberg, (2002).

[7] H. Kwakernaak, Fuzzy random variables, algorithms and examples for the discrete case, Information Sciences, 7, 253-278, (1979).


[8] J. Holland, Adaptation in Natural and Artificial System, University of Michigan Press, Ann Arbor, MI, (1975).

[9] J.E. Beasley and P.C. Chu, A genetic algorithm for the set covering problem, European Journal of Operational Research, vol. 94, 3920404, (1996).