Rodionov A.S.
Are there possibilities for further speeding up calculation of a random graph reliability indicators?
The report discusses new methods for accelerating the calculation of some characteristics of the connectivity of a random graph (the probability of a subset of vertices being connected, the average probability of a pairwise connection, mathematical expectation of the size of a connected subgraph containing a selected vertex, and some others). These problems have a proven non-polynomial complexity and, as a rule, approximate solutions are sought. However, with the development of computer technology and the development of parallel algorithms, finding exact solutions has become possible for graphs of a sufficiently large dimension to solve practical problems (up to hundreds of vertices in the case of their small average degree). In addition, the solutions to these problems found over the years, including by the author of the report, various methods of reduction and decomposition made it possible to further increase the dimension of the calculated graphs. Exact solutions are also needed to examine the quality of approximate algorithms.
Various techniques are proposed for the development of the well-known factorization method, when instead of considering one pivot edge, a certain small subset of edges chosen in a special way is considered.
To reports list