基于二元决策图的网络可靠性评估

Network reliability evaluation based on binary decision diagrams

提出一种改进二元决策图(BDD)的网络可靠性评估方法.为了解决BDD构造中有效识别同构子图的问题,将边收缩/删除法应用于BDD的图分解中,并提出了BDD的宽度优先搜索算法,通过遍历BDD图对边进行排序,为布尔函数的不交化提供了一种新的高效途径.实验结果表明,该算法具有精确性高、时间复杂度低的优点,可以避免常规最小路算法中进行不交化的大量运算,并可应用于一些大规模的网络.

An improved method for evaluating the network reliability based on binary decision diagrams（BDD） is presented. To solve the structure in the effective identification of BDD subgraph isomorphism problem, the edge contraction/deletion is applied to this decomposition process of network graphs, and the width first search algorithm of BDD is proposed. By traversing BDD graph, the edges are sorted. A new and efficient way is provided for the Boolean function disjoint. The experiment results show that, the algorithm has the merit of high accuracy and low time complexity, and can avoid a large number of disjoint operations in the minimum path algorithm, which can be applied to a number of large-scale networks.