生成有向装配连接图有向割集的递归收缩算法

• 论文 •

生成有向装配连接图有向割集的递归收缩算法

梁勇强，钟艳如，张庆霞

1．玉林师范学院职业技术学院，广西玉林537000；2．桂林电子科技大学计算机系，广西桂林541004

出版日期:2008-02-15 发布日期:2008-02-25

Recursive contraction algorithm for enumerating all directed cutsets of a directional assembly connection graph

LIANG Yong-qiang, ZHONG Yan-ru, ZHANG Qing-xia

1.School of Profession & Technology, Yulin Normal Univeristy, Yulin 537000, China; 2.Department of Computer Science, Guilin University of Electronic Technology, Guilin 541004, China

Online:2008-02-15 Published:2008-02-25

摘要/Abstract

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

关键词: 有向装配连接图, 有向割集, 递归收缩算法

Abstract: 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.

Key words: directed assembly connection graph, directed cutsets, recursive contraction algorithm

中图分类号:

TP391.73

梁勇强，钟艳如，张庆霞. 生成有向装配连接图有向割集的递归收缩算法[J]. .

LIANG Yong-qiang, ZHONG Yan-ru, ZHANG Qing-xia. Recursive contraction algorithm for enumerating all directed cutsets of a directional assembly connection graph[J]. .