A Li~ear-T~~e Algorithm to
Antohe Rauzy · 1996
A module of a fault tree is a subtree whose ter- minal 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 fmd 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.