Reduced Recursive Sum of Disjoint Product in Network Reliability  
Author Shin-Guang Chen

 
Co-Author(s)  

 
Abstract The probability of union events is always an important research topic in the scienti c areas. Many real life ap- plications use such probability in their core implementa- tions. The most popular method to calculate the prob- ability of union events is the inclusion-exclusion princi- ple (IEP), which originates from the idea of Abraham de Moivre (1718). However, the computation complexity is ex- act O(2n) no matter what the events are. In 2007, a much ecient method namely Recursive Sum of Disjoint Product (RSDP) was proposed by Zuo et al. (Zuo, M. J.; Tian, Z. and Huang, H. Z., An ecient method for reliability evalu- ation of multistate networks given all minimal path vectors, IIE Transactions, 39:811-817, 2007.) The computation com- plexity is also O(2n) in the worse cases, but it usually has 10 times eciency than IEP in normal cases. This paper proposed a reduced version of RSDP, which can obtain over 100 times eciency than RSDP in normal cases, and in the worse cases, it has at least the same complexity as that of RSDP. A comparison among them is presented to show the eciency of the proposed method.

 
Keywords Union event, probability, stochastic- ow network, reliability, minimal cut, minimal path
   
    Article #:  20170
 
Proceedings of the 20th ISSAT International Conference on Reliability and Quality in Design
August 7-9, 2014 - Seattle, Washington, U.S.A.