Approximation Algorithm of Arrangement Graph Reliability in Parallel System

In parallel system, the arrangement graph A_n,k has good properties such as symmetry, small diameter, and high fault tolerance. Subsystem reliability is defined as the probability that there is still a normal operating subsystem when the system has faults. It is usually used to measure the system health status, and the calculation of subsystem reliability is an NP-hard problem. This paper discusses the robustness of the reliability of the subgraphs and the approximate algorithm of reliability. Further, the Monte Carlo algorithm for arrangement graphs is constructed. The simulation results show that the constructed Monte Carlo algorithm is much better than the known approximation algorithm. In particular, the error of Monte Carlo approximation of A_3,2 subgraph reliability is less than 1%.