Abstract:

The computational complexity of the BDD (Binary Decision Diagram) based network reliability method is linear correlated to the size of BDD that heavily depends on the quality of edge ordering.Because it is still NP-hard to find the optimum edge ordering, heuristic ordering methods such as BFS (BreadthFirstSearch) or DFS (DepthFirstSearch) are commonly used in practice.For the edge ordering strategy, boundary set is first used to analyze the characteristics of constructing BDD,and then a high performance edge ordering strategy based on the boundary set is proposed.Several experiments show that the new strategy outperforms the classic methods such as DFS and BFS.The results extend new space for network reliability analysis method using BDD in largescale networks.

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