On type-2 fuzzy weighted minimum spanning tree. (English) Zbl 1498.05228
Summary: This article investigates the notion of a minimum spanning tree (MST) of an undirected type-2 fuzzy weighted connected graph (UT2FWCG), where the edge weights are represented as discrete type-2 fuzzy variables. A modified type-2 fuzzy Borüvka’s algorithm (MT2FBA) is proposed to determine an MST of UT2FWCG. The effective weight of the MST is calculated, and its defuzzified value is compared with an equivalent MST with deterministic weights. The working principle of the algorithm includes ranking, addition operation and defuzzification of discrete type-2 fuzzy variables. The defuzzified effective weight of the MST is determined using the critical value (CV)-based type reduction technique and centroid method. The proposed algorithm is numerically illustrated with suitable examples. Moreover, the simulation results of nine random instances of UT2FWCG are also studied to analyze the proposed MT2FBA properly.
MSC:
| 05C72 | Fractional graph theory, fuzzy graph theory |
| 05C35 | Extremal problems in graph theory |
| 05C05 | Trees |
Keywords:
minimum spanning tree; type-2 fuzzy variable; satisfaction function; CV-based type reduction; defuzzification; Borüvka’s algorithmReferences:
| [1] | Antonelli, M.; Bernardo, D.; Hagras, H., Multi-objective evolutionary optimization of type-2 fuzzy rule-based systems for financial data classification, IEEE Trans Fuzzy Syst, 25, 2, 249-264 (2017) · doi:10.1109/TFUZZ.2016.2578341 |
| [2] | Anusuya, V.; Sathya, R., A new approach for solving type-2 fuzzy shortest path problem, Ann Pure Appl Math, 8, 1, 83-92 (2014) |
| [3] | Assad, A.; Xu, W., The quadratic minimum spanning tree problem, Nav Res Logist, 39, 3, 399-417 (1992) · Zbl 0769.90078 · doi:10.1002/1520-6750(199204)39:3<399::AID-NAV3220390309>3.0.CO;2-0 |
| [4] | Blue, M.; Bush, B.; Puckett, J., Unified approach to fuzzy graph problems, Fuzzy Sets Syst, 125, 355-368 (2002) · Zbl 1014.90077 · doi:10.1016/S0165-0114(01)00011-2 |
| [5] | Borüvka, O., O jistém problem minimálním, Práce Moravské Přírodovĕdecké Společnosti V, I, 4, 57-63 (1930) |
| [6] | Chiang, TC; Liu, CH; Huang, YM, A near-optimal multicast scheme for mobile ad hoc networks using a hybrid genetic algorithm, Expert Syst Appl, 33, 3, 734-742 (2007) · doi:10.1016/j.eswa.2006.06.020 |
| [7] | Dhamdhere, K.; Ravi, R.; Singh, M.; Jünger, M.; Kaibel, V., On two-stage stochastic minimum spanning trees, Integer programming and combinatorial optimization IPCO 2005. lecture notes in computer science, 321-334 (2005), Heidelberg: Springer, Heidelberg · Zbl 1119.90359 · doi:10.1007/11496915_24 |
| [8] | Di Puglia, PL; Guerriero, F.; Santos, JL, Dynamic programming for spanning tree problems: application to the multi-objective case, Optim Lett, 9, 3, 437-450 (2015) · Zbl 1317.90312 · doi:10.1007/s11590-014-0759-1 |
| [9] | Gao, X.; Jia, L., Degree constrained minimum spanning tree problem with uncertain edge weights, Appl Soft Comput, 56, 580-588 (2017) · doi:10.1016/j.asoc.2016.07.054 |
| [10] | Gao, J.; Lu, M., Fuzzy quadratic minimum spanning tree problem, Appl Math Comput, 164, 3, 773-788 (2005) · Zbl 1099.90082 |
| [11] | Gower, JC; Ross, GJS, Minimum spanning trees and single linkage cluster analysis, J R Statist Soc Ser C Appl Statist, 18, 1, 54-64 (1969) |
| [12] | Ishii, H.; Shiode, S.; Nishida, T.; Namasuya, Y., Stochastic spanning tree problem, Discret Appl Math, 3, 4, 263-273 (1981) · Zbl 0466.90056 · doi:10.1016/0166-218X(81)90004-4 |
| [13] | Ishii, H.; Matsutomi, T., Confidence regional method of stochastic spanning tree problem, Math Comput Model, 22, 10, 77-82 (1995) · Zbl 0844.62025 · doi:10.1016/0895-7177(95)00183-3 |
| [14] | Itoh, T.; Ishii, H., An approach based on necessity measure to the fuzzy spanning tree problems, J Oper Res Soc Japan, 39, 2, 247-257 (1996) · Zbl 0863.90135 |
| [15] | Janiak, A.; Kasperski, A., The minimum spanning tree problem with fuzzy costs, Fuzzy Optim Decis Mak, 7, 2, 105-118 (2008) · Zbl 1169.90492 · doi:10.1007/s10700-008-9030-5 |
| [16] | Kayacan, E.; Sarabakha, A.; Coupland, S.; John, R.; Khanesar, MA, Type-2 fuzzy elliptic membership functions for modeling uncertainty, Eng Appl Artif Intell, 70, 170-183 (2018) · doi:10.1016/j.engappai.2018.02.004 |
| [17] | Kruskal, JB Jr, On the shortest spanning subtree of a graph and traveling salesman problem, Proc Am Math Soc, 7, 1, 48-50 (1956) · Zbl 0070.18404 · doi:10.1090/S0002-9939-1956-0078686-7 |
| [18] | Kumar, R.; Jha, S.; Singh, S., Shortest path problem in network with type-2 triangular fuzzy arc length, J Appl Res Ind Eng, 4, 1, 1-7 (2017) |
| [19] | Kundu, P.; Kar, S.; Maiti, M., Fixed charge transportation problem with type-2 fuzzy variables, Inf Sci, 255, 170-186 (2014) · Zbl 1321.90022 · doi:10.1016/j.ins.2013.08.005 |
| [20] | Lee, S.; Lee, KH, Shortest path problem in a type-2 weighted graph, J Korea Fuzzy Intell Syst Soc, 11, 6, 528-531 (2001) |
| [21] | Lee, S.; Lee, KH; Lee, D., Comparison of type-2 fuzzy values with satisfaction function, Int J Uncert Fuzziness Knowl Based Syst, 12, 5, 601-611 (2004) · Zbl 1065.03509 · doi:10.1142/S0218488504003107 |
| [22] | Liu, B., Uncertainty theory (2007), Berlin: Springer, Berlin · Zbl 1141.28001 |
| [23] | Liu, B.; Liu, Y-K, Expected value of fuzzy variable and fuzzy expected value models, IEEE Trans Fuzzy Syst, 10, 4, 445-450 (2002) · doi:10.1109/TFUZZ.2002.800692 |
| [24] | Liu ZQ, Liu Y-K (2007) Fuzzy possibility space and type-2 fuzzy variable. In: FOCI 2007 IEEE symposium on foundations of computational intelligence, Honolulu, HI, USA pp. 616-621. doi:10.1109/FOCI.2007.371536. |
| [25] | Liu, ZQ; Liu, Y-K, Type-2 fuzzy variables and their arithmetic, Soft Comput, 14, 729-747 (2010) · Zbl 1214.68401 · doi:10.1007/s00500-009-0461-x |
| [26] | Majumder S (2019) Some network optimization models under diverse uncertain environments. Doctoral dissertation, National Institute of Technology Durgapur, Durgapur, West Bengal, India, arxiv.2103.08327 |
| [27] | Majumder, S.; Kar, S.; Pal, T.; Mandal, J.; Mukhopadhyay, S.; Dutta, P., Mean-entropy model of uncertain portfolio selection problem, Multi-Objective Optimization (2018), Singapore: Springer, Singapore · Zbl 1409.91216 |
| [28] | Majumder, S.; Kar, S.; Pal, T., Rough-fuzzy quadratic minimum spanning tree problem, Expert Syst, 36, 2, 1-29 (2019) · doi:10.1111/exsy.12364 |
| [29] | Majumder, S.; Kar, S.; Pal, T., Uncertain multi-objective Chinese postman problem, Soft Comput, 23, 11557-11572 (2019) · Zbl 1436.90105 · doi:10.1007/s00500-018-03697-3 |
| [30] | McDonald R, Pereira F, Ribarov K, Hajič J (2005) Non-projective dependency parsing using spanning tree algorithms. In: Proceedings of the Conference on Human Language Technology and Empirical Methods in Natural Language Processing, pp. 523-530. Association for Computational Linguistics, Stroudsburg, PA, USA. |
| [31] | Mendel, JM, Computing with words: Zadeh, Turing, Popper and Occam, IEEE Comput Intell Mag, 2, 4, 10-17 (2007) · doi:10.1109/MCI.2007.9066897 |
| [32] | Mendel, JM, Advances in type-2 fuzzy sets and systems, Inf Sci, 177, 1, 84-110 (2007) · Zbl 1117.03060 · doi:10.1016/j.ins.2006.05.003 |
| [33] | Mendel, JM; John, RIB, Type-2 fuzzy sets made simple, IEEE Trans Fuzzy Syst, 10, 2, 117-127 (2002) · doi:10.1109/91.995115 |
| [34] | Mendel, JM; John, RI; Liu, FL, Interval type-2 fuzzy logical systems made simple, IEEE Trans Fuzzy Syst, 14, 6, 808-821 (2006) · doi:10.1109/TFUZZ.2006.879986 |
| [35] | Nguyen, T.; Khosravi, A.; Creighton, D.; Nahavnadi, S., Medical data classification using interval type-2 fuzzy logic system and wavelets, Appl Soft Comput, 30, 812-822 (2015) · doi:10.1016/j.asoc.2015.02.016 |
| [36] | Öncan, T., Design of capacitated minimum spanning tree with uncertain cost and demand parameters, Inf Sci, 177, 20, 4354-4367 (2007) · doi:10.1016/j.ins.2007.02.023 |
| [37] | Prim, RC, Shortest connection networks and some generalizations, Bell Syst Tech J, 36, 6, 1389-1401 (1957) · doi:10.1002/j.1538-7305.1957.tb01515.x |
| [38] | Shukla, AK; Muhuri, PK, Big data clustering with internal type-2 fuzzy Uncertainty modelling in gene expression datasets, Eng Appl Artif Intell, 77, 268-282 (2019) · doi:10.1016/j.engappai.2018.09.002 |
| [39] | Stam, CJ; Tewarie, CJ; Van Straaten, ECW; Hillebrand, A.; Van Mieghem, P., The trees and the forest: Characterization of complex brain networks with minimum spanning trees, Int J Psychophysiol, 92, 3, 129-138 (2014) · doi:10.1016/j.ijpsycho.2014.04.001 |
| [40] | Torkestani, JA, Degree constrained minimum spanning tree problem: a learning automata approach, J Supercomput, 64, 1, 226-249 (2013) · Zbl 1286.68296 · doi:10.1007/s11227-012-0851-1 |
| [41] | Torkestani, JA; Meybodi, MR, A learning automata-based heuristic algorithm for solving the minimum spanning tree problem in stochastic graphs, J Supercomput, 59, 2, 1035-1054 (2012) · doi:10.1007/s11227-010-0484-1 |
| [42] | Türkşen, IB, Type 2 representation and reasoning for CWW, Fuzzy Sets Syst, 127, 1, 17-36 (2002) · Zbl 1006.68134 · doi:10.1016/S0165-0114(01)00150-6 |
| [43] | Qin, R.; Liu, Y-K; Liu, Z-Q, Methods of critical value reduction for type-2 fuzzy variables and their applications, J Comput Appl Math, 235, 5, 1454-1481 (2011) · Zbl 1204.26051 · doi:10.1016/j.cam.2010.08.031 |
| [44] | Xu, Y.; Uberbache, EC, 2D image segmentation using minimum spanning trees, Image vis Comput, 15, 1, 47-57 (1997) · doi:10.1016/S0262-8856(96)01105-5 |
| [45] | Yager, RR, A procedure for ordering fuzzy subsets of the unit interval, Inf Sci, 24, 2, 143-161 (1981) · Zbl 0459.04004 · doi:10.1016/0020-0255(81)90017-7 |
| [46] | Zadeh, LA, The concept of a linguistic variable and its application to approximate reasoning—I, Inf Sci, 8, 3, 199-249 (1975) · Zbl 0397.68071 · doi:10.1016/0020-0255(75)90036-5 |
| [47] | Zadeh, LA, Fuzzy sets as a basis for a theory of possibility, Fuzzy Sets Syst, 1, 1, 3-28 (1978) · Zbl 0377.04002 · doi:10.1016/0165-0114(78)90029-5 |
| [48] | Zhou, J.; Chen, L.; Wang, K., Path optimality conditions for minimum spanning tree problem with uncertain edge weights, Int J Uncert Fuzziness Knowl-Based Syst, 23, 1, 49-71 (2015) · Zbl 1323.05062 · doi:10.1142/S0218488515500038 |
| [49] | Zhou, J.; Chen, L.; Wang, K.; Yang, F., Fuzzy α-minimum spanning tree problem: definition and solutions, Int J Gen Syst, 45, 3, 311-335 (2016) · Zbl 1353.90135 · doi:10.1080/03081079.2015.1086578 |
| [50] | Zhou, J.; Yi, X.; Wang, K.; Liu, J., Uncertain distribution-minimum spanning tree problem, Int J Uncert Fuzziness Knowl Based Syst, 24, 4, 537-560 (2016) · Zbl 1377.90104 · doi:10.1142/S0218488516500264 |
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
