Analysis of two-terminal network reliability based on efficient data structure
Tóm tắt
The present work is depend upon a different data structure to perform the network reliability estimation efficiently. Zero suppressed binary decision diagram (ZBDD) is an well ordered and effective method of representing not only the boolean functions but also the sets of combinations than the conventional binary decision diagrams (BDD). This paper proposes new algorithm to manipulate the ZBDDs the variant of BDD on some benchmark networks. The 2-terminal network reliability problem has been studied extensively and effective results have been obtained.
Tài liệu tham khảo
Akers SB (1978) Binary decision diagrams. IEEE Trans Comput 1(6):509–516
Ball MO (1986) Computational complexity of network reliability analysis: an overview. IEEE Trans Reliab 35(3):230–239
Ball MO, Colbourn CJ, Provan JS (1995) Network reliability, network models. Handbook of operations research. Elsevier, North Holland, pp 673–762
Bryant RE (1986) Graph based algorithms for Boolean function manipulation. IEEE Trans Comput C 35(8):677–691
Bryant RE (1992) Symbolic boolean manipulation with ordered binary decision diagrams. ACM Comput Surv (CSUR) 24(3):293–318
Colbourn CJ (1987) The combinatorics of network reliability. Oxford University Press Inc, New York
Hardy G, Lucet C, Limnios N (2007) K-terminal network reliability measures with binary decision diagrams. IEEE Trans Reliab 56(3):506–515
Hariri S, Raghavendra S (1987) Syrel: a symbolic reliability algorithm based on path and cutest methods. IEEE Trans Comput 10:1224–1232
Kobayashi K, Yamamoto H (1999) A new algorithm in enumerating all minimal paths in a sparse network. Reliab Eng Syst Saf 65(1):11–15
Kuo SY, Lu SK, Yeh FM (1999) Determining terminal-pair reliability based on edge expansion diagrams using OBDD. IEEE Trans Reliab 48(3):234–246
Kuo SY, Yeh FM, Lin HY (2007) Efficient and exact reliability evaluation for networks with imperfect vertices. IEEE Trans Reliab 56(2):288–300
Lee CY (1959) Representation of switching circuits by binary-decision programs. Bell Syst Tech J 38(4):985–999
Lu JM, Innal F, Wu XY, Liu Y, Lun dteigen MA (2016) Two-terminal reliability analysis for multi-phase communication networks. Eksploatacja I Niezawodnosc 18(3):418–427
Minato SI (1993) Zero-suppressed BDDs for set manipulation in combinatorial problems. In: 30th ACM/IEEE design automation conference, pp 272–277
Minato SI (2001) Zero-suppressed BDDs and their applications. Int J Softw Tools Technol Transf 3(2):156–170
Misra R, Chaturvedi SK (2009) A cutset based unified framework to evaluate network reliability measures. IEEE Trans Reliab 58(4):658–666
Nguyen D, Vo B, Vu DL (2016) A parallel strategy for the logical-probabilistic calculus-based method to calculate two-terminal reliability. Qual Reliab Eng Int 32(7):2313–2327
Pino W, Gomes T, Kooij R (2015) A comparison between two all-terminal reliability algorithms. J Adv Comput Netw 3(4):284–290
Rauzy A (1993) New algorithms for fault tree analysis. Reliab Eng Syst Saf 40(3):203–211
Rauzy A (2003) A New methodology to handle boolean models with loops. IEEE Trans Reliab 52(1):96–105
Satyanarayana A, Chang MK (1983) Network reliability and the factoring theorem. Networks 13(1):107–120
Shen Y (1995) A new simple algorithm for enumerating all minimal paths and cuts of a graph. Microelectron Reliab 35(6):973–976
Singh H, Vaithilingam S, Anne K (1996) Terminal reliability using binary decision diagrams. Microelectron Reliab 36(3):363–365
Soh S, Rai S (1991) CAREL: computer aided reliability evaluator for distributed computing networks. IEEE Trans Parallel Distrib Syst 2(2):199–213
Soh S, Rai S (1993) Experimental results on preprocessing of path/cut terms in sum of disjoint product techniques. IEEE Trans Reliab 42(1):24–33
Somenzi F (2012) CUDD: CU decision diagram package: Release 2.5.0. http://vlsi.colorado.edu/~fabio/CUDD/
Thayse A, Davio M, Deschamps JP (1978) Optimization of multiple-valued decision diagrams. ISMVL-8, pp 171–177
Theologou O, Carlier J (1991) Factoring and reductions for networks with imperfect vertices. IEEE Trans Reliab 40(2):210–217
Veeraraghavan M, Trivedi KS (1991) An improved algorithm for symbolic reliability analysis. IEEE Trans Reliab 40(3):347–358
Venkata Ramana B, Chatterjee S, Vishwakarma GK (2017) Estimation of network reliability using optimal ROBDD approach. ARS Combinatoria (Accepted)
Yeh FM, Lu SK, Kuo SY (2002) OBDD-based evaluation of k-terminal network reliability. IEEE Trans Reliab 51(4):443–451
Zang X, Sun N, Trivedi KS (1999) A BDD-based algorithm for reliability analysis of phased mission systems. IEEE Trans Reliab 48(1):50–60
Zhang Z, Shao F (2018) A diameter-constrained approximation algorithm of multistate two-terminal reliability. IEEE Trans Reliab 67(3):1249–1260
Zhu P, Guo Y, Lombardi F, Han J (2017) Approximate reliability of multi-state two-terminal networks by stochastic analysis. IET Netw 6(5):116–124