Abstract
We consider the problem of a network reliability calculation for a network with unreliable communication links and perfectly reliable nodes. For such networks, we study two different reliability indices: network average pairwise connectivity and average size of a connected subgraph that contains some special vertex. The problem of precise calculation of both these characteristics is known to be NP-hard. Both indices may be calculated or estimated through complete or partial enumeration of pairs of vertexes and calculation of their pairwise reliability. Methods for speeding up this process in the case when there are chains in a graph structure are presented in the paper.
D.A. Migov—This research was supported by Russian Foundation for Basic Research under grant 16-37-00345 and by grant of the Program of basic researches of the Presidium of Russian Academy of Science.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
References
Bollobas, B.: Random Graphs, 2nd edn. Cambridge University Press, Cambridge (2001). http://dx.doi.org/10.1017/CBO9780511814068
Colbourn, C.J.: The Combinatorics of Network Reliability. Oxford University Press Inc., New York (1987)
Gadyatskaya, O., Rodionov, A.S., Rodionova, O.K.: Using EDP-polynomials for network structure optimization. In: Gervasi, O., Murgante, B., Laganà, A., Taniar, D., Mun, Y., Gavrilova, M.L. (eds.) ICCSA 2008, Part II. LNCS, vol. 5073, pp. 1061–1076. Springer, Heidelberg (2008)
Jereb, L.: Network reliability: models, measure and analysis. In: Proceedings of the 6th IFIP Workshop on Performance Modeling and Evaluation of ATM Networks, pp. T02/1–T02/10 (1998)
Lucet, C., Manouvrier, J.F.: Exact methods to compute network reliability. In: Ionescu, D.C., Limnios, N. (eds.) Statistical and Probabilistic Models in Reliability, pp. 279–294. Birkhäuser Boston, Boston (1999). http://dx.doi.org/10.1007/978-1-4612-1782-4_20
Page, L., Perry, J.: A practical implementation of the factoring theorem for network reliability. IEEE Trans. Reliab. 37(3), 259–267 (1988)
Petingi, L.A.: Reliability study of mesh networks modeled as random graphs. In: Proceedings of the 2010 International Conference on Mathematical Models for Engineering Science, MMES 2010, Stevens Point, Wisconsin, USA, pp. 85–93. World Scientific and Engineering Academy and Society (WSEAS) (2010). http://dl.acm.org/citation.cfm?id=1965658.1965688
Potapov, A., Goemann, B., Wingender, E.: The pairwise disconnectivity index as a new metric for the topological analysis of regulatory networks. BMC Bioinform. 9, 227 (2008). http://dx.doi.org/10.1186/1471-2105-9-227
Sun, F., Shayman, M.: On the average pairwise connectivity of wireless multihop networks. In: 2005 Global Telecommunications Conference, GLOBECOM 2005, vol. 3, p. 5. IEEE, November 2005
Tauro, S.L., Palmer, C.R., Siganos, G., Faloutsos, M.: A simple conceptual model for the internet topology. In: 2001 Proceedings of the Global Telecommunications Conference, GLOBECOM 2001, 25–29 November 2001, San Antonio, TX, USA, pp. 1667–1671 (2001). http://dx.doi.org/10.1109/GLOCOM.2001.965863
Won, J.M., Karray, F.: Cumulative update of all-terminal reliability for faster feasibility decision. IEEE Trans. Reliab. 59(3), 551–562 (2010)
Xie, M., Dai, Y., Poh, K.: Computing Systems Reliability: Models and Analysis. Kluwer, Dordrecht (2004)
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2016 Springer International Publishing Switzerland
About this paper
Cite this paper
Rodionov, A.S., Migov, D.A. (2016). New Advantages of Using Chains in Computing Multiple \(s-t\) Probabilistic Connectivity. In: Gervasi, O., et al. Computational Science and Its Applications – ICCSA 2016. ICCSA 2016. Lecture Notes in Computer Science(), vol 9787. Springer, Cham. https://doi.org/10.1007/978-3-319-42108-7_9
Download citation
DOI: https://doi.org/10.1007/978-3-319-42108-7_9
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-42107-0
Online ISBN: 978-3-319-42108-7
eBook Packages: Computer ScienceComputer Science (R0)