IEICE TRANSACTIONS on Fundamentals
A Factored Reliability Formula for Directed Source-to-All-Terminal Networks
Summary :
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 tu generate the optimal factored formula, which contains no identical product terms.
- Publication
- IEICE TRANSACTIONS on Fundamentals Vol.E77-A No.1 pp.134-143
- Publication Date
- 1994/01/25
- Publicized
- Online ISSN
- DOI
- Type of Manuscript
- Special Section PAPER (Special Section on Reliability)
- Category
- System Reliability
Authors
Keyword
Latest Issue
Copyrights notice of machine-translated contents
The copyright of the original papers published on this site belongs to IEICE. Unauthorized use of the original or translated papers is prohibited. See IEICE Provisions on Copyright for details.
Cite this
Copy
Yoichi HIGASHIYAMA, Hiromu ARIYOSHI, Isao SHIRAKAWA, Shogo OHBA, "A Factored Reliability Formula for Directed Source-to-All-Terminal Networks" in IEICE TRANSACTIONS on Fundamentals,
vol. E77-A, no. 1, pp. 134-143, January 1994, doi: .
Abstract: 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 tu generate the optimal factored formula, which contains no identical product terms.
URL: https://global.ieice.org/en_transactions/fundamentals/10.1587/e77-a_1_134/_p
Copy
@ARTICLE{e77-a_1_134,
author={Yoichi HIGASHIYAMA, Hiromu ARIYOSHI, Isao SHIRAKAWA, Shogo OHBA, },
journal={IEICE TRANSACTIONS on Fundamentals},
title={A Factored Reliability Formula for Directed Source-to-All-Terminal Networks},
year={1994},
volume={E77-A},
number={1},
pages={134-143},
abstract={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 tu generate the optimal factored formula, which contains no identical product terms.},
keywords={},
doi={},
ISSN={},
month={January},}
Copy
TY - JOUR
TI - A Factored Reliability Formula for Directed Source-to-All-Terminal Networks
T2 - IEICE TRANSACTIONS on Fundamentals
SP - 134
EP - 143
AU - Yoichi HIGASHIYAMA
AU - Hiromu ARIYOSHI
AU - Isao SHIRAKAWA
AU - Shogo OHBA
PY - 1994
DO -
JO - IEICE TRANSACTIONS on Fundamentals
SN -
VL - E77-A
IS - 1
JA - IEICE TRANSACTIONS on Fundamentals
Y1 - January 1994
AB - 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 tu generate the optimal factored formula, which contains no identical product terms.
ER -
English
