Document Type : Research Paper

Author

Department of Mathematics, University Maragheh, Maragheh, Iran.

Abstract

The inherent feature of real-world data is uncertainty. If data is generated in valid experiments or standard collections, probability theory or fuzzy theory is a powerful tool for analyzing them. But data is not always reliable, especially when it is not possible to perform a reliable test or data collection multiple times. In this situations, referring to the beliefs of experts in the field in question is an alternative approach and uncertainty theory is a tool by which the beliefs of experts can be mathematically incorporated into the problem-solving structure. In this paper, we investigate the finding minimum weighted maximal matching with uncertain weights. For this purpose, we offer two methods. In the first method, by introducing the concept of chance constraint, we obtain model with definite coefficients. The second method is based on the concept of uncertain expected value. Finally, a numerical example for these two methods is presented. 

Keywords

[1] A. Munaro, ‎ On some classical and new hypergraph invariants. PhD thesis‎, ‎Universite Grenoble Alpes‎, ‎2016.
[2] C. Bozeman‎, B. ‎Brimkov‎, C. ‎Erickson‎, D. ‎Ferrero‎, M. ‎Flagg‎, and L. Hogben, ‎ Restricted power domination and zero forcing problems. J. Combin. Optim.‎, ‎37(3)‎, ‎(2019)‎, pp. ‎935-956.
[3] ‎A‎. Brandstädt‎, ‎ Efficient domination and efficient edge domination‎: ‎A brief survey‎.  ‎In Conference on Algorithms and Discrete Applied Mathematics, ‎(2018‎‎),‎ pp‎. ‎1-14,‎ ‎Springer‎, ‎Cham.
[4] ‎A. Droschinsky‎, ‎ ‎P. ‎Mutzel ‎ ‎and ‎E‎. Thordsen‎, ‎ ‎ Shrinking trees not blossoms‎: ‎A recursive maximum matching approach. In 2020 Proceedings of the Twenty-Second Workshop on Algorithm Engineering and Experiments (ALENEX) ‎(2020), pp‎. ‎146-160, ‎Society for Industrial and Applied Mathematics‎.
[5] ‎V‎. ‎L. do Forte‎, ‎M‎. ‎C. ‎Lin‎, ‎A.‎ ‎Lucena‎, ‎N.‎ ‎Maculan‎, ‎V‎. ‎A. ‎Moyano and ‎J‎. ‎L‎. Szwarcfiter‎, ‎ Modelling and solving the perfect edge domination problem. Optim. Lett.‎, ‎14(2)‎, ‎(2020)‎, pp. ‎369-394‎.
[6] ‎S. Gupta‎, ‎P. ‎Misra‎,‎ ‎S. ‎Saurabh‎, ‎ ‎and ‎M‎. Zehavi‎, ‎‎ ‎Popular matching in roommates setting is NP-hard‎. ‎In Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms ‎(2019), pp‎. ‎2810-2822‎. ‎Society for Industrial and Applied Mathematics.
[7] ‎B. Liu‎, ‎and‎ ‎Y‎. ‎K‎. Liu‎, Expected value of fuzzy variable and fuzzy expected value models‎. ‎IEEE. Trans. Fuzzy. Syst.‎, ‎10(4)‎, ‎(2002), pp. ‎445-450.
[8] ‎B‎. Liu‎, Uncertainty theory., Vol 154, ‎Springer, ‎2007.
[9] B‎. Liu, ‎ Uncertainty theory‎, ‎Vol 24, ‎Springer‎, ‎2015.
[10] ‎Z. Pan‎, ‎Y. ‎Yang‎, ‎X. ‎Li and ‎S‎. ‎J‎. Xu‎, ‎ The complexity of total edge domination and some related results on trees. J. Combin. Optim.‎, ‎40(3)‎, ‎(2020)‎, pp. ‎571-589.
[11] ‎S. Har-Peled and ‎K‎. Quanrud‎, Approximation algorithms for polynomial-expansion and low-density graphs. SIAM J. Comput.‎, ‎46(6)‎, ‎(2017)‎v, pp. ‎1712-1744.