关键词: 二进制决策图, 网络可靠度, 边扩展路径

Abstract:

BDD is a diagrammatic representation of the Boolean function and has been widely applied to the network reliability analysis.In order to enhance the performance of network reliability analysis algorithm based on BDD,this paper first puts forward two kinds of invalid edge expansion paths according to the edge expansion diagram instance:invalid edge expansion with redundant nodes and invalid edge expansion with ST unconnectedness.Then,useful techniques are provided to successfully eliminate those invalid edge expansion paths.Experimental results show that these techniques can identify the invalid paths in advance,avoid invalid extension,reduce the number of intermediate subnetworks and shorten the analysis time.With these two techniques,both of the invalid expansion paths can be eliminated,and hence great performance improvement of network reliability analysis is achieved.

Key words: binary decision diagram(BDD);network reliability;edge expansion paths