An O(n*log(n)) algorithm to compute the all-terminal reliability of (K/sub 5/, K/sub 2.2.2/) free networks

摘要

A graph is (K/sub 5/, K/sub 2.2.2/) free if it has no subgraph contractible to K/sub 5/ or K/sub 2.2.2/. The class of partial 3-trees (also known as Y- Delta graphs) is a proper subset of (K/sub 5/, K/sub 2.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 (K/sub 5/, K/sub 2.2.2/) free graphs on n points. The running time of this algorithm is O(n) if G is planar.