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

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

Network reliability evaluation based on binary decision diagrams

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.