General information
Latest issue
Impact factor

Search papers
Search references

Latest issue
Current issues
Archive issues
What is RSS

Prikl. Diskr. Mat.:

Personal entry:
Save password
Forgotten password?

Prikl. Diskr. Mat., 2020, Number 47, Pages 62–86 (Mi pdm695)  

Applied Graph Theory

Vertex decomposition to calculate the network probabilistic connectivity

D. A. Migov

Institute of Computational Mathematics and Mathematical Geophysics of SB RAS, Novosibirsk, Russia

Abstract: We consider the problem of calculating such an indicator of network reliability as the random graph probabilistic connectivity. It is assumed that the edges of the network are subject to failures that occur independently of each other with given probabilities. Network nodes are assumed to be absolutely reliable. The possibility of using network decomposition via vertex cuts for the network reliability calculation is investigated. By cut we mean a set of network elements, the removal of which makes the network disconnected. The history of the development of such methods is given, and the place of our results is indicated among them. The results related to the case of two nodes cuts are presented in detail, including the results of the author and R. K. Wood (1985). Next, we consider the cuts of arbitrary power. The results in this area were obtained by the author (2004–2008) and J. M. Burgos (2016). Also, certain results using cuts were obtained by the author for the cumulative bounds updating of the random graph probabilistic connectivity (2012) and for the diameter constrained reliability calculation (2011–2012). Author results include the general method, which gives the formulas expressing the reliability of a network with a vertex cut through the reliabilities of its subnets obtained by cut decomposition, as well as through reliabilities of the subnets, contracted by all possible variants over cut vertices. On its basis, we derive such formulas for cuts of two, three, and four vertices. Some of the results of the author were previously published; some results are published for the first time, including the correct formula for four vertices cut and the valid proof of the solvability of a system of linear equations, which guarantees the existence of the above mentioned formulas. The results of numerical experiments showing the applicability of the proposed methods are given. For example, using the 3 cut formula the reliability calculation of the 3$\times$16 grid shows an acceleration of about 120 times compared with the factoring method. For biconnected structures, a mathematical apparatus and an algorithm are given that make it possible to effectively take into account all two-vertex sections when calculating their reliability. Without such an approach we should use above mentioned cut formulas recursively, for graphs obtained by cut decomposition and for these graphs contracted by all possible variants over cut vertices. This inevitably leads to recalculation of reliability for certain graphs. Using the proposed algorithm allows to avoid such recalculation and additionally speeds up the reliability calculation for suitable network structures.

Keywords: network reliability, random graph, probabilistic connectivity, factoring method, network decomposition, vertex cut, edge cut.

Funding Agency Grant Number
Russian Foundation for Basic Research 18-07-00460_а
Russian Academy of Sciences - Federal Agency for Scientific Organizations 0315-2016-0006


Full text: PDF file (1227 kB)
References: PDF file   HTML file

UDC: УДК 519.17+519.24

Citation: D. A. Migov, “Vertex decomposition to calculate the network probabilistic connectivity”, Prikl. Diskr. Mat., 2020, no. 47, 62–86

Citation in format AMSBIB
\by D.~A.~Migov
\paper Vertex decomposition to calculate the network probabilistic connectivity
\jour Prikl. Diskr. Mat.
\yr 2020
\issue 47
\pages 62--86

Linking options:

    SHARE: FaceBook Twitter Livejournal

    Citing articles on Google Scholar: Russian citations, English citations
    Related articles on Google Scholar: Russian articles, English articles
  • Прикладная дискретная математика
    Number of views:
    This page:59
    Full text:8

    Contact us:
     Terms of Use  Registration  Logotypes © Steklov Mathematical Institute RAS, 2020