Some New Ideas About Obtaining and Estimating Reliability Polynomial of a Random Graph

摘要

In this paper some new ideas are presented concerning speeding up calculation of coefficients of all-terminal reliability polynomial (CRPs) of an undirected random graph with reliable nodes and unreliable links. Along with the task of obtaining exact values of CRPs , the task of their fast estimation is discussed. We try estimate CRPs in one of possible representations of reliability polynomial (RP) based on their meaning and counting all a fortiori connected and disconnected states of a graph using easily obtained information. We show how several steps of known exact methods anticipatory to calculation of CRPs bounds increase their quality.