AN O(N.LOG(N)) ALGORITHM TO COMPUTE THE ALL-TERMINAL RELIABILITY OF (K(5), K(2),2,2) FREE NETWORKS

A graph is (K5, K2,2,2) free if it has no subgraph contractible to K5 or K2,2,2. The class of partial 3-trees (also known as Y-DELTA graphs) is a proper subset of (K5, K2,2,2) free graphs. Let G be a network with perfectly reliable points and edges that fail independently with some known probabilities. The all-terminal reliability R(G) of G is the probability that G is connected. Computing R(G) for a general network is NP-hard. This paper presents an O(n.log(n)) algorithm to compute R(G) of any (K5, K2,2,2) free graphs on n points. The running time of this algorithm is O(n) if G is planar.