International Society of Science and Applied Technologies |
|
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 scientic 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 |
August 7-9, 2014 - Seattle, Washington, U.S.A. |