Calculation of the reliability of extended tri-connected networks

When analyzing the reliability of networks for various purposes, the apparatus of random graphs is usually used. The most common indicator of reliability is the probability of connectivity of a random graph with unreliable edges, which describes the reliability of a network in terms of the ability to establish a connection between each pair of network nodes. However, the problem of calculating the probability of network connectivity is NP-hard. To reduce the dimensional when carrying out precise calculations, methods based on the use of structural features of networks are widely used, primarily various methods of reduction and decomposition. Networks with an extended structure are used in number of applications. These are, for example, networks located in extended objects - mines, ships, other objects. Linear wireless sensor networks, designed for monitoring various long-distance objects, such as pipelines, bridges, roads, also have an extended structure. Despite their linear physical structure, the topological graph of such a network can be either linear or non-linear, since wireless communication channels are possible not only between the nearest neighboring nodes. For example, if each node can communicate with three nodes on the right and three nodes on the left, we obtain a network containing a group of three-vertex cross separators. If the graph of an extended network is linear, then calculating its probabilistic connectivity is not difficult. The use of a serial-parallel transformation, or other techniques, allows us to make the calculation within polynomial complexity. If the network graph is biconnected and contains a separators of two nodes, then the calculation can be significantly accelerated by using decomposition along these separators. In this paper, we study the possibility of quickly calculating the reliability of extended three-connected networks using decomposition according to the previously proposed formula. Such decomposition will lead to the production of 10 new extended graphs of a smaller size. As experiments have shown, this approach is quite effective and makes it possible to calculate the reliability of extended networks, for which it is not possible to calculate the reliability using an accurate method.