On distribution function of the diameter in uncertain graph. (English) Zbl 1360.05131
Summary: In uncertain graphs, the existence of some edges is not predetermined. The diameter of an uncertain graph is essentially an uncertain variable, which indicates the suitability for investigation of its distribution function. The main focus of this paper is to propose an algorithm to determine the distribution function of the diameter of an uncertain graph. We first discuss the characteristics of the uncertain diameter, and the distribution function is derived. An efficient algorithm is designed based on Floyd’s algorithm. Further, some numerical examples are illustrated to show the efficiency and application of the algorithm.
MSC:
| 05C72 | Fractional graph theory, fuzzy graph theory |
| 05C85 | Graph algorithms (graph-theoretic aspects) |
Keywords:
uncertainty modeling; graph theory; uncertain graph; distribution function; Floyd’s algorithmSoftware:
Algorithm 97References:
| [1] | Bargiela, A.; Pedrycz, W., Toward a theory of granular computing for human-centered information processing, IEEE Trans. Fuzzy Syst., 12, 320-330 (2008) |
| [2] | Bhattacharya, P., Some remarks on fuzzy graphs, Pattern Recogn. Lett., 6, 297-302 (1987) · Zbl 0629.05060 |
| [3] | Bollobás, B., Modern Graph Theory (1998), Springer-Verlag: Springer-Verlag New York · Zbl 0902.05016 |
| [4] | Chen, J.; Li, J., An application of rough sets to graph theory, Inf. Sci., 201, 114-127 (2012) · Zbl 1251.05165 |
| [5] | Dempster, A., Upper and lower probabilities induced by a multivalued mapping, Ann. Math. Stat., 38, 2, 325-339 (1967) · Zbl 0168.17501 |
| [6] | Ding, S., Uncertain multi-product newsboy problem with chance constraint, Appl. Math. Comput., 223, 139-146 (2013) · Zbl 1329.90009 |
| [8] | Dubois, D.; Prade, H., Possibility Theory: An Approach to Computerized Processing of Uncertainty (1988), Plenum: Plenum New York · Zbl 0703.68004 |
| [9] | Erdös, P.; Rényi, A., On random graphs I, Publ. Math. Debrecen, 6, 290-297 (1959) · Zbl 0092.15705 |
| [10] | Erdös, P.; Rényi, A., On the evolution of random graphs, Bull. Int. Stat. Inst., 5, 17-61 (1960) · Zbl 0103.16301 |
| [11] | Floyd, R., Algorithm-97-shortest path, Commun. ACM, 5, 6, 345 (1962) |
| [12] | Gilbert, E., Random graphs, Ann. Math. Stat., 30, 4, 1141-1144 (1959) · Zbl 0168.40801 |
| [13] | Gao, X.; Gao, Y., Connectedness of uncertain graph, Int. J. Uncertainty Fuzz. Knowl.-Based Syst., 21, 1, 127-137 (2013) · Zbl 1325.05098 |
| [14] | Gao, Y., Shortest path problem with uncertain arc lengths, Comput. Math. Appl., 62, 6, 2591-2600 (2011) · Zbl 1231.90367 |
| [15] | Gao, Y.; Wen, M.; Ding, S.; (s, S) policy for uncertain single period inventory problem, Int. J. Uncertainty Fuzz. Knowl.-Based Syst., 21, 6, 945-953 (2013) · Zbl 1401.90029 |
| [16] | Gao, Y., Uncertain models for single facility location problems on networks, Appl. Math. Model., 36, 6, 2592-2599 (2012) · Zbl 1246.90083 |
| [17] | Gong, Z.; Sun, B.; Chen, D., Rough set theory for the interval-valued fuzzy information systems, Inf. Sci., 178, 8, 1968-1985 (2008) · Zbl 1138.68564 |
| [18] | Han, S.; Peng, Z.; Wang, S., The maximum flow problem of uncertain network, Inf. Sci., 265, 167-175 (2014) · Zbl 1328.90018 |
| [19] | He, T.; Xue, P.; Shi, K., Application of rough graph in relationship mining, J. Syst. Eng. Electron., 19, 4, 742-747 (2008) · Zbl 1223.05299 |
| [20] | Kahneman, D.; Tversky, A., Prospect theory: an analysis of decision under risk, Econometrica, 47, 2, 263-292 (1979) · Zbl 0411.90012 |
| [21] | Liu, B., Uncertainty Theory (2007), Springer-Verlag: Springer-Verlag Berlin · Zbl 1141.28001 |
| [22] | Liu, B., Some research problems in uncertainty theory, J. Uncertain Syst., 3, 1, 3-10 (2009) |
| [23] | Liu, B., Uncertainty Theory: A Branch of Mathematics for Modeling Human Uncertainty (2010), Springer-Verlag: Springer-Verlag Berlin |
| [24] | Newman, M., Random graphs with clustering, Phys. Rev. Lett., 103, 5 (2009), art. no. 058701 |
| [25] | Newman, M., The structure of scientific collaboration networks, Proc. Natl. Acad. Sci. USA, 98, 404-409 (2001) · Zbl 1065.00518 |
| [26] | Pawlak, Z., Rough sets, Int. J. Parallel Prog., 11, 5, 341-356 (1982) · Zbl 0501.68053 |
| [27] | Pedrycz, W., Granular Computing: Analysis and Design of Intelligent Systems (2013), CRC Press/Francis Taylor: CRC Press/Francis Taylor Boca Raton |
| [28] | Qin, Z.; Kar, S., Single-period inventory problem under uncertain environment, Appl. Math. Comput., 219, 18, 9630-9638 (2013) · Zbl 1290.90007 |
| [29] | Rosenfeld, A., Fuzzy graphs, (Zadeh, L.; Fu, K.; Tanaka, K.; Shimura, M., Fuzzy sets and their applications to cognitive and decision processes (1975), Academic Press: Academic Press New York), 77-95 · Zbl 0315.05131 |
| [30] | Serrano, M.; Bogun¨á, M., Clustering in complex networks: I. General formalism, Phys. Rev. E, 74 (2006), art. no. 056114 |
| [31] | Sheng, Y.; Yao, K., Fixed charge transportation problem in uncertain environment, Ind. Eng. Manage. Syst., 11, 2, 183-187 (2012) |
| [32] | Sheng, Y.; Yao, K., A transportation model with uncertain costs and demands, Inf.: Int. Interdiscipl. J., 15, 8, 3179-3186 (2012) · Zbl 1323.90010 |
| [33] | Tversky, A.; Kahneman, D., Rational choice and the framing of decisions, J. Bus., 59, 2, 251-278 (1986) |
| [34] | Watts, D.; Strogatz, S., Collective dynamics of small-world networks, Nature, 393, 440-442 (1998) · Zbl 1368.05139 |
| [35] | West, D., Introduction to Graph Theory (2001), Pearson Education, Inc: Pearson Education, Inc Singapore |
| [36] | Yang, L.; Liu, P.; Li, S.; Gao, Y.; Ralescu, D., Reduction methods of type-2 uncertain variables and their applications to solid transportation problem, Inf. Sci., 291, 204-237 (2015) · Zbl 1355.68267 |
| [37] | Zadeh, L., Fuzzy sets, Inf. Control, 8, 338-353 (1965) · Zbl 0139.24606 |
| [38] | Zadeh, L., Outline of a new approach to the analysis of complex systems and decision processes, IEEE Trans. Syst. Man Cybern., 3, 28-44 (1973) · Zbl 0273.93002 |
| [39] | Zhang, B.; Peng, J., Uncertain programming model for chinese postman problem with uncertain weights, Ind. Eng. Manage. Syst., 11, 1, 18-25 (2012) |
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.
