@article {
author = {Li, Hui and Zhang, Bo and Peng, Jin},
title = {ON THE MATCHING NUMBER OF AN UNCERTAIN GRAPH},
journal = {Iranian Journal of Fuzzy Systems},
volume = {15},
number = {2},
pages = {89-108},
year = {2018},
publisher = {University of Sistan and Baluchestan},
issn = {1735-0654},
eissn = {2676-4334},
doi = {10.22111/ijfs.2018.3761},
abstract = {Uncertain graphs are employed to describe graph models with indeterministicinformation that produced by human beings. This paper aims to study themaximum matching problem in uncertain graphs.The number of edges of a maximum matching in a graph is called matching numberof the graph. Due to the existence of uncertain edges, the matching number of an uncertain graph is essentially an uncertain variable.Different from that in a deterministic graph, it is more meaningful to investigate the uncertain measure that an uncertain graph is $k$-edge matching (i.e., the matching number is greater than or equal to $k$).We first study the properties of the matching number of an uncertain graph, and then give a fundamental formula for calculating the uncertain measure. We further prove that the fundamental formula can be transformedinto a simplified form. What is more, a polynomial time algorithm to numerically calculate the uncertain measure is derived from the simplified form.Finally, some numerical examples are illustrated to show the application and efficiency of the algorithm.},
keywords = {Uncertainty theory,Uncertain measure,Maximum matching,Matching number,Uncertain graph},
url = {https://ijfs.usb.ac.ir/article_3761.html},
eprint = {https://ijfs.usb.ac.ir/article_3761_843af24ca521b1d9f207a6a79751dcc4.pdf}
}