POLYNOMIAL-TIME COMPUTABILITY OF THE EDGE-RELIABILITY OF GRAPHS USINGGILBERTS FORMULA

Reliability is an important consideration in analyzing computer and ot her communication networks, but current techniques are extremely limit ed in the classes of graphs which can be analyzed efficiently. While G ilbert's formula establishes a theoretically elegant recursive relatio nship between the edge reliability of a graph and the reliability of i ts subgraphs, naive evaluation requires consideration of all sequences of deletions of individual vertices, and for many graphs has time com plexity essentially Theta (N!). We discuss a general approach which si gnificantly reduces complexity, encoding subgraph isomorphism in a fin er partition by invariants, and recursing through the set of invariant s.We illustrate this approach using threshhold graphs, and show that a ny computation of reliability using Gilbert's formula will be polynomi al-time if and only if the number of invariants considered is polynomi al; we then show families of graphs with polynomial-time, and non-poly nomial reliability computation, and show that these encompass most pre viously known results. We then codify our approach to indicate how it can be used for other classes of graphs, and suggest several classes t o which the technique can be applied.