中文摘要：

为解决有向装配图有向割集的求解,给出一个生成有向装配连接图有向割集的高效算法,该算法优先考虑检查有向割集两个子图间边的方向。算法首先利用边收缩图的概念,递归生成有向装配连接图的具有一个连通子图的一部分有向断集,接着通过判断另一个子图是否连通,从这些有向断集的集合中筛选出全部的有向割集。理论分析和实验分析均表明,该改进算法可行且高效,时间复杂度明显低于已有算法。

英文摘要：

To resolve directed cutset of Directed Assembly Connection Graph （DACG）, an efficient algorithm for the enumeration of all directed cutsets of DACG was presented. This algorithm recursively enumerated a part of DACG directed segs which had one connected subgraph by using the theory of edge contraction. And then all directed cutsets from the set of those directed segs were selected by analyzing connectivity of another subgraph. Theoretical analysis and experimental analysis of the algorithm showed that the improved algorithm was feasible and efficient. Time complexity of the improved algorithm was much lower than existing algorithms.