Asymptotic Formulas for Connectivity Probabilities of Random Graphs

摘要

Known asymptotic formulas are used to analyze the connectivity probability of graphs with highly reliable and poorly reliable edges. The conventional methods used to calculate the coefficients in these formulas require a number of arithmetic operations that grows geometrically with the growing number of graph edges. The adjacency matrix of the dual graph for highly reliable edges and the Kirchhoff matrix for poorly reliable edges result in algorithms of cubic complexity.