Using Delta-Wye Transformations for Estimating Networks’ Reliability

Abstract

It is well-known that finding the exact reliability polynomial of a given two-terminal network in general is a highly demanding computational task (belonging to the $\#P$-complete class of problems), while for particular networks this process might get to be significantly simpler (e.g., of polynomial complexity). This statement is especially true in the case of (very) large networks which cannot be reduced to compositions of simpler (e.g., series and parallel) networks, e.g., those containing complex bridge-type sub-networks. A promising, and not much explored approach, is to borrow concepts and methods from electrical circuits, in particular the delta-wye transformation which has long been established and used for computing exactly the equivalent resistance of a resistor network. We shall review how such concepts (from electronics) should be adapted and applied to reliability evaluations, showing that (as opposed to the case of electrical circuits) these are not always exact, hence sometimes leading to reliability estimates. We shall exemplify approximations of the reliability polynomials when using delta-wye transformations, and show that this approach is able to significantly reduce complexity. Finally, we will apply the delta-wye transformation method to the Moore-Shannon hammock networks (for the first time ever), and show how hammock networks can be transformed into ladder networks/graphs whose reliability can be easily computed by a recurrence formula. Illustrative examples revealing the accuracy of this type of approximation will also be presented.