Abstract
The new algorithmic technique which allow higher efficiency in the precise calculation of the reliability of an undirected graph with absolutely reliable nodes and unreliable edges is considered in this paper. As graph’s reliability we mean its probabilistic connectivity. The proposed technique is based on the reduction of the dimension of a calculated graph by considering its node’s cuts. Comprehensive computer simulation results show the advantages of the proposed algorithms, that the calculation time decreases significantly in comparison with existent methods.
Chapter PDF
Similar content being viewed by others
Keywords
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
References
Rodionova, O.K., Rodionov, A.S., Choo, H.: Network Probabilistic Connectivity: Exact Calculation with Use of Chains. In: Laganá, A., Gavrilova, M.L., Kumar, V., Mun, Y., Tan, C.J.K., Gervasi, O. (eds.) ICCSA 2004. LNCS, vol. 3046, pp. 315–324. Springer, Heidelberg (2004)
Moore, E.F., Shannon, C.E.: Reliable Circuits Using Less Reliable Relays. J. Franclin Inst. 262, 191–208 (1956)
Shooman, A.M., Kershenbaum, A.: Exact Graph-Reduction Algorithms for Network Reliability Analysis. In: Proc. GLOBECOM 1991, vol. 2, pp. 1412–1420 (1991)
Shooman, A.M.: Algorithms for Network Reliability and Connection Availability Analysis. Electro/95 Int. Professional Program Proc. 309–333 (1995)
Rodionov, A.S., Choo, H.: On Generating Random Network Structures: Connected Graphs. In: Proceedings of the International Conference on Information Networking ICOIN 2004, vol. III, pp. 1145–1152 (2004)
Koide, T., Shinmori, S., Ishii, H.: Topological optimization with a network reliability constraint. Discrete Appl. Math. 115(1-3), 135–149 (2001)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2006 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Migov, D.A., Rodionova, O.K., Rodionov, A.S., Choo, H. (2006). Network Probabilistic Connectivity: Using Node Cuts. In: Zhou, X., et al. Emerging Directions in Embedded and Ubiquitous Computing. EUC 2006. Lecture Notes in Computer Science, vol 4097. Springer, Berlin, Heidelberg. https://doi.org/10.1007/11807964_71
Download citation
DOI: https://doi.org/10.1007/11807964_71
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-36850-2
Online ISBN: 978-3-540-36851-9
eBook Packages: Computer ScienceComputer Science (R0)