关键词: 网络可靠度, 二叉决策图, 边界集, 边排序

Abstract:

The computational complexity of network reliability analysis based on the Binary Decision Diagram (BDD) is closely related to the size of BDD, which depends crucially on the quality of edge ordering. So it is of importance to find the best edge ordering that attempts to minimize the memory using BDD manipulation. However, it is still NPhard to find the optimal edge ordering. In practice,heuristic ordering methods such as BreadthFirstSearch (BFS ) or DepthFirstSearch (DFS )，which are suitable for different types of networks, are commonly used.Unfortunately,no formal guidelines or factors which determine the quality of edge ordering are available for choosing a better heuristic approach for the given network. In this work,characterizing the Boundary Set Length (BSL) as the quality of edge ordering, we reveal the relationship between the BSL and the size of BDD.Empirical studies show that the BSL has positive correlation with the size of BDD.This means the smaller the BSL of an edge ordering, the smaller the size of BDD model generated. In most cases, the size of the BDD can get (or be close to) the extreme value when the BSL has its extreme one. This conclusion is useful for choosing or designing high performance edge ordering for a given network.

Key words: network reliability;binary decision diagram(BDD);boundary set;edge ordering.