# zbMATH — the first resource for mathematics

The maximum fuzzy weighted matching models and hybrid genetic algorithm. (English) Zbl 1152.05358
Summary: A matching of a graph is an independent subset of the edges set and a maximum matching is a matching with as many edges in it as possible. The maximum weighted matching problem is to find a maximum matching in a given graph such that the sum of the weights of the edges in it is maximum. In this paper, the concepts of expected maximum fuzzy weighted matching, the $$\alpha$$-maximum fuzzy weighted matching and the most maximum fuzzy weighted matching are initialized. According to various decision criteria, the maximum fuzzy weighted matching problem is formulated as expected value model, chance-constrained programming and dependent-chance programming by using the credibility theory, and the crisp equivalents are also given. Furthermore, a hybrid genetic algorithm is designed for solving the proposed fuzzy programming models. Finally, a numerical example is given.

##### MSC:
 05C70 Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) 05C85 Graph algorithms (graph-theoretic aspects)
Full Text:
##### References:
  Balakrishnarajan, M.; Venuvanaligam, P., An artificial intelligence approach for the generation and enumeration of perfect matching on graphs, Comput. math. appl., 29, 115-121, (1995)  Balas, E.; Pulleybank, W., The perfectly matchable subgraph polytope of an arbitrary graph, Combinatorica, 9, 321-337, (1989) · Zbl 0723.05087  Bondy, J.A.; Murty, U.S.R., Graph theory with application, (1976), The Macmillan Press Ltd. · Zbl 1134.05001  Boulmakoul, A., Generalized path-finding algorithms on semirings and the fuzzy shortest path problem, J. comput. appl. math., 162, 263-272, (2004) · Zbl 1038.90103  Chanas, S.; Delgado, M., Fuzzy optimal flow on imprecise structure, Eur. J. oper. res., 83, 568-580, (1995) · Zbl 0899.90086  Charnes, A.; Copper, W.W., Chance-constrained programming, Manage. sci., 6, 73-79, (1959) · Zbl 0995.90600  Diamond, P., A fuzzy MAX-flow MIN-cut theorem, Fuzzy sets syst., 119, 139-148, (2001) · Zbl 1044.90531  Dubois, D.; Prade, H., Possibility theory: an approach to computerized processing of uncertainty, (1988), Plenum New York  Galil, Z., Efficient algorithms for finding maximal matchings in graphs, Comput. surveys, 18, 23-38, (1986) · Zbl 0606.68064  Gen, M.; Cheng, R., Genetic algorithms & engineering optimization, (2000), John & Sonc, Inc. New York  Hsieh, A.; Ho, C.; Fan, K., An extension of the bipartite weighted matching problem, Pattern recognition lett., 16, 347-353, (1995)  Hsieh, A.; Fan, K.; Fan, T., Bipartite weighted matching for on-line handwritten Chinese character recognition, Pattern recognition, 28, 143-151, (1995)  Kim, J.; Wormal, Ni, Random matchings which induce Hamilton cycles and Hamiltonian decompositions of random regular graphs, J. combin. theory (ser. B), 81, 20-44, (2001) · Zbl 1030.05107  Lamb, J., A note on the weighted matching with penalty problem, Pattern recognition lett., 19, 261-263, (1998) · Zbl 0905.68129  Liu, B., Uncertainty theory: an introduction to its axiomatic foundations, (2004), Springer-Verlag Berlin · Zbl 1072.28012  Liu, B.; Liu, Y.K., Expected value of fuzzy variable and fuzzy expected value models, IEEE trans. fuzzy syst., 10, 445-450, (2002)  Liu, B.; Iwamura, K., Chance constrained programming with fuzzy parameters, Fuzzy sets syst., 94, 227-237, (1998) · Zbl 0923.90141  Liu, B.; Iwamura, K., A note on chance constrained programming with fuzzy coefficients, Fuzzy sets syst., 100, 229-233, (1998) · Zbl 0948.90156  Liu, B., Minimax chance constrained programming models for fuzzy decision systems, Inform. sci., 112, 25-38, (1998) · Zbl 0965.90058  Liu, B., Dependent-chance programming with fuzzy decisions, IEEE trans. fuzzy syst., 7, 3, 354-360, (1999)  Liu, B., Theory and practice of uncertain programing, (2002), Physica-Verlag New York  Liu, B., Toward fuzzy optimization without mathematical ambiguity, Fuzzy optim. decision making, 1, 43-63, (2002) · Zbl 1068.90618  Lozin, V., On maximum induced matchings in bipartite graphs, Inform. process. lett., 81, 7-11, (2002) · Zbl 1046.68081  Okada, S., Fuzzy shortest path problems incorporating interactivity among paths, Fuzzy sets syst., 142, 335-357, (2004) · Zbl 1045.90092  Okada, S.; Soper, T., A shortest path problem on a network with fuzzy arc lengths, Fuzzy sets syst., 109, 129-140, (2000) · Zbl 0956.90070  Rosenbloom, A., On the sets of perfect matchings for two bipartite graphs, Inform. process. lett., 70, 95-97, (1999) · Zbl 1002.68066  Steiner, G.; Yeomans, G., A linear time algorithm for maximum matching in convex, bipartite graphs, Comput. math. appl., 31, 91-96, (1996) · Zbl 0851.68090  Zito, M., Small maximal matchings in random graphs, Theor. comput. sci., 297, 487-507, (2003) · Zbl 1044.68138  Zadeh, L.A., Fuzzy sets, Inform. control, 8, 338-353, (1965) · Zbl 0139.24606
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.