Italiano (Italian) English (Inglese)
venerdì, 15 dicembre 2017

Rapporti Tecnici

Dettagli rapporto tecnico
Autori:Marco Beccuti
Susanna Donatelli
Giuliana Franceschinis
Roberta Terruggia
Area Scientifica:Dependability and Reliability
Performance Evaluation
Titolo:A new symbolic approach for network reliability analysis
Apparso su:TR-INF-2011-06-02-UNIPMN
Editore:Computer Science Department, UPO
Anno:2011
URL:http://www.di.unipmn.it...R-INF-2011-06-02-UNIPMN.pdf
Sommario: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.