(K, J)-DOMINATION AND (K, J)-RELIABILITY

The (K, j)-reliability of a K-terminal network G is the probability th at after the failure of some of its edges the vertices in K will lie i n no more than j connected components of the resulting subnetwork of G ; when j = 1, this is the usual K-terminal reliability of G. In this p aper, we extend the well-known theory of reliability domination and it s application to the analysis of factoring algorithms for the computat ion of K-terminal reliability to (K, j)-reliability and the associated notion of (K, j) -domination. We give conditions equivalent to two ed ges being parallel or in series with respect to (K, j)-reliability, an d we characterize the networks of (K, j)-domination less than or equal to 3. (C) 1997 John Wiley & Sons, Inc.