A method for generating a factored formula of SAT network

摘要

In a probabilistic network, souroe-to-all-termi-nal (SAT) reliability may be denned as the probability that there exists at least on path consisting only of successful arcs from source vertex s to every other vertex. This paper describes a strategy to get an optimal formula being a product of the reliability formulas of vertex-section graphs, each of which contains a distinct strongly connected component of given graph. This method reduces the computing cost and data processing effort required to generate a simple factored formula, which contains no identical formula.