×

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)
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] 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)
[2] Balas, E.; Pulleybank, W., The perfectly matchable subgraph polytope of an arbitrary graph, Combinatorica, 9, 321-337, (1989) · Zbl 0723.05087
[3] Bondy, J.A.; Murty, U.S.R., Graph theory with application, (1976), The Macmillan Press Ltd. · Zbl 1134.05001
[4] 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
[5] Chanas, S.; Delgado, M., Fuzzy optimal flow on imprecise structure, Eur. J. oper. res., 83, 568-580, (1995) · Zbl 0899.90086
[6] Charnes, A.; Copper, W.W., Chance-constrained programming, Manage. sci., 6, 73-79, (1959) · Zbl 0995.90600
[7] Diamond, P., A fuzzy MAX-flow MIN-cut theorem, Fuzzy sets syst., 119, 139-148, (2001) · Zbl 1044.90531
[8] Dubois, D.; Prade, H., Possibility theory: an approach to computerized processing of uncertainty, (1988), Plenum New York
[9] Galil, Z., Efficient algorithms for finding maximal matchings in graphs, Comput. surveys, 18, 23-38, (1986) · Zbl 0606.68064
[10] Gen, M.; Cheng, R., Genetic algorithms & engineering optimization, (2000), John & Sonc, Inc. New York
[11] Hsieh, A.; Ho, C.; Fan, K., An extension of the bipartite weighted matching problem, Pattern recognition lett., 16, 347-353, (1995)
[12] Hsieh, A.; Fan, K.; Fan, T., Bipartite weighted matching for on-line handwritten Chinese character recognition, Pattern recognition, 28, 143-151, (1995)
[13] 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
[14] Lamb, J., A note on the weighted matching with penalty problem, Pattern recognition lett., 19, 261-263, (1998) · Zbl 0905.68129
[15] Liu, B., Uncertainty theory: an introduction to its axiomatic foundations, (2004), Springer-Verlag Berlin · Zbl 1072.28012
[16] Liu, B.; Liu, Y.K., Expected value of fuzzy variable and fuzzy expected value models, IEEE trans. fuzzy syst., 10, 445-450, (2002)
[17] Liu, B.; Iwamura, K., Chance constrained programming with fuzzy parameters, Fuzzy sets syst., 94, 227-237, (1998) · Zbl 0923.90141
[18] Liu, B.; Iwamura, K., A note on chance constrained programming with fuzzy coefficients, Fuzzy sets syst., 100, 229-233, (1998) · Zbl 0948.90156
[19] Liu, B., Minimax chance constrained programming models for fuzzy decision systems, Inform. sci., 112, 25-38, (1998) · Zbl 0965.90058
[20] Liu, B., Dependent-chance programming with fuzzy decisions, IEEE trans. fuzzy syst., 7, 3, 354-360, (1999)
[21] Liu, B., Theory and practice of uncertain programing, (2002), Physica-Verlag New York
[22] Liu, B., Toward fuzzy optimization without mathematical ambiguity, Fuzzy optim. decision making, 1, 43-63, (2002) · Zbl 1068.90618
[23] Lozin, V., On maximum induced matchings in bipartite graphs, Inform. process. lett., 81, 7-11, (2002) · Zbl 1046.68081
[24] Okada, S., Fuzzy shortest path problems incorporating interactivity among paths, Fuzzy sets syst., 142, 335-357, (2004) · Zbl 1045.90092
[25] 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
[26] Rosenbloom, A., On the sets of perfect matchings for two bipartite graphs, Inform. process. lett., 70, 95-97, (1999) · Zbl 1002.68066
[27] 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
[28] Zito, M., Small maximal matchings in random graphs, Theor. comput. sci., 297, 487-507, (2003) · Zbl 1044.68138
[29] 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.