Parallel Methods for Network Reliability Calculation and Cumulative Updating of Network Reliability Bounds

摘要

We consider the problem of network reliability calculation for a network with unreliable communication links and perfectly reliable nodes. This problem is known to be NP-hard. Based on the well-known factoring method, we introduce a parallel method for network reliability calculation. Another approach we study is a cumulative updating of lower and upper bounds of network reliability for faster feasibility decision of a given network without performing exhaustive calculation. A parallel implementation of this method is proposed. The analysis of the numerical experiments allowed us to set some important parameters of the parallel algorithms for speeding up calculations.