Fuzzy Maximum Independent Set Problem of Graphic

Abstract:

Edge covering problem, dominating set problem, and independent set problem are classic problems in graph theory except for vertex covering problem. In this paper, we study the maximum independent set problem under fuzzy uncertainty environments, which aims to search for the independent set with maximum value in a graph. First, credibility theory is introduced to describe the fuzzy variable. Three decision models are performed based on the credibility theory. A hybrid intelligence algorithm which integrates genetic algorithm and fuzzy simulation is proposed due to the unavailability of traditional algorithm. Finally, numerical experiments are performed to prove the efficiency of the fuzzy decision modes and the hybrid intelligence algorithm.

• Periodical: Applied Mechanics and Materials (Volumes 687-691)
• Pages: 1657-1661
• DOI: https://doi.org/10.4028/www.scientific.net/AMM.687-691.1657
• Online since: November 2014
• Authors: Dong Ling Luo*, Chen Yin Wang, Yang Yi, Dong Ling Zhang, Xiao Cong Zhou
• Keywords: Credibility Theory, Fuzzy Simulation, Fuzzy Variable, Genetic Algorithm (GA), Maximum Independent Problem

References

[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).

DOI: 10.1007/3-540-61680-2_55

[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).

DOI: 10.1145/513800.513821

[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).

DOI: 10.1016/j.apm.2007.04.007

[6] B. Liu, Uncertainty Theory: An Introduction to its Axiomatic Foundations, Springer-Verlag, Berlin, (2004).

[7] B. Liu and Y. Liu, Expected value of fuzzy variable and fuzzy expected value models, IEEE Transactions on Fuzzy Systems, Vol. 10, No. 4, 445-450, (2002).

DOI: 10.1109/tfuzz.2002.800692

[8] B. Liu and K. Iwamura, Chance constrained programming with fuzzy parameters, Fuzzy Sets and Systems, Vol. 94, No. 2, 227-237, (1998).

DOI: 10.1016/s0165-0114(96)00236-9

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

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