A FACTORED RELIABILITY FORMULA FOR DIRECTED SOURCE-TO-ALL-TERMINAL NETWORKS

In a probabilistic graph (network), source-to-all-terminal (SAT) relia bility may be defined as the probability that there exists at least on e path consisting only of successful arcs from source vertex s to ever y other vertex. In this paper, we define an optimal SAT reliability fo rmula to be the one with minimal number of literals or operators. At f irst, this paper describes an are-reductions (open- or short-circuitin g) method for obtaining a factored formula of directed graph. Next, we discuss a simple strategy to get an optimal formula being a product o f the reliability formulas of vertex-section graphs, each of which con tains a distinct strongly connected component of the given graph. This method reduces the computing cost and data processing effort required to generate the optimal factored formula, which contains no identical product terms.