A Factored Reliability Formula for Directed Source-to-All-Terminal Networks (Special Section on Reliability)

概要

論文の詳細を見る
In a probabilistic graph (network), source-to-all-terminal (SAT) reliability may be defined as the probability that there exists at least one path consisting only of successful arcs from source vertex s to every other vertex. In this paper, we define an optimal SAT reliability formula to be the one with minimal number of literals or operators. At first, this paper describes an arc-reductions (open-or short-circuiting) method for obtaining a factored formula of directed graph. Next, we discuss a simple 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 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.
社団法人電子情報通信学会の論文
1994-01-25