| Abstract: | In this paper we propose a new approach for network reliability analysis based on Binary Decision Diagrams (BDDs). This approach can be summarized in three steps: first, we encode on a BDD the rules generating the minpaths of a specific graph and we use it to efficiently derive a BDD encoding the minpaths. Then, the minpath BDD is translated in the BDD encoding the connectivity function using an approach based on saturation strategy. Finally, we use the classical algorithm to compute the network reliability from BDD encoding the connectivity function and the probability of the edges to be connected. In this way, we are able to reduce the computation memory peak with respect to already developed approaches which build directly the BDD encoding the connectivity function. Finally, a set of experiments comparing, in terms of memory utilization and computation time, the proposed approach with respect to others approaches building directly a BDD encoding the connectivity function. |
