Factoring and reductions for networks with imperfect vertices

Abstract

Factoring and reductions are effective methods for computing the K-terminal reliability of undirected networks, but they have been applied mostly to networks with perfect vertices. However, in real problems, vertices may fail as well as edges. Imperfect vertices can be factored like edges, but the complexity then increases exponentially with their number. A technique has been developed to account for the failure of vertices with small additional cost, using a modified method of factoring and reductions. This technique is very easy to integrate into a factoring algorithm. It consists of factoring not on a single element (e.g., a single edge) but on a set of elements (e.g., an edge and its endpoints). The problem is that random variables associated with the elements of the network are no longer independent. This can be handled by choosing factoring edges that have at least one perfect endpoint. This technique leaves the factoring algorithm practically unchanged. The only difference is that some supplementary probability values are kept for the imperfect vertices of the original and the induced graphs. For algorithms using simple reductions, it has negligible computational cost.< <ETX xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">&gt;</ETX>