The K-terminal reliability is the probability that all K-vertices in a stochastic network are connected. A divide-and-conquer approach using separating vertex sets in order to compute this reliability is presented. Since the complexity of the splitting formula increases exponentially with the size of the separating vertex set, only graphs with a small separating vertex set lend to efficient computation by this approach. However, this approach can be used to establish lower and upper bounds for the K-terminal reliability of stochastic networks. Various bounds derived from a splitting method presented by Bienstock in 1986 are provided. For some example networks the exact value and lower and upper bounds for the all-terminal reliability and the two-terminal reliability are computed.
