A linear-time algorithm to find modules of fault trees
A linear-time algorithm to find modules of fault trees
复制标题
DOI：
10.1109/24.537011
复制
发表时间：
1996-09-01
影响因子：
5.9
通讯作者：
Rauzy, A
中科院分区：
文献类型：
--
作者：
Dutuit, Y;Rauzy, A
故障树的模块是其终端事件不会在树中的其他位置发生的子树，即模块。为了减少故障树上基本运算的计算量，如根事件概率的计算或最小割集的计算，本文提出了一种线性时间算法来检测故障树的模块，该算法是从寻找图的强连通分支的Tarjan算法衍生而来的。在真实故障树的基准测试上，我们的方法在个人计算机上证明了我们的方法可以在几毫秒内检测到具有数百个门的树的模块和事件。
A module of a fault tree is a subtree whose terminal events do not occur elsewhere in the tree, Modules. which are independent subtrees, can be used to reduce the computational cost of basic operations on fault trees, such as the computation of the probability of the root event or the computation of the minimal cut sets, This paper presents a linear time algorithm to detect modules of a fault tree, coherent or not, that is derived from the Tarjan algorithm to find strongly connected components of a graph, We show, on a benchmark of real fault trees, that our method detects modules of trees with several hundred gates and events within few milliseconds on a personal computer.