Finding the minimum weighted maximal matching of a graph with uncertain weights

Indeterminacy is an intrinsic characteristic of real-world data. Where they originate from credible experiments, probability theory is a robust tool to manipulate this type of indeterminacy. However, this is not always the case, and referring to the domain expert belief is an alternative pproach. Baoding Liu initiated an axiomatic basis of uncertainty theory to answer this kind of indeterminacy. Minimum weighted maximal matching has wide range of applications in many fields. In this paper, we investigate this problem with indeterministic weights and obtain an equivalent deterministic integer programming model.

Keywords:

Integer programming , Minimum weighted maximal matching , Uncertainty theory