-
题名生成有向装配连接图有向割集的递归收缩算法
被引量:1
- 1
-
-
作者
梁勇强
钟艳如
张庆霞
-
机构
玉林师范学院职业技术学院
桂林电子科技大学计算机系
-
出处
《计算机集成制造系统》
EI
CSCD
北大核心
2008年第2期329-335,共7页
-
基金
国家自然科学基金资助项目(60563005)~~
-
文摘
为解决有向装配图有向割集的求解,给出一个生成有向装配连接图有向割集的高效算法,该算法优先考虑检查有向割集两个子图间边的方向。算法首先利用边收缩图的概念,递归生成有向装配连接图的具有一个连通子图的一部分有向断集,接着通过判断另一个子图是否连通,从这些有向断集的集合中筛选出全部的有向割集。理论分析和实验分析均表明,该改进算法可行且高效,时间复杂度明显低于已有算法。
-
关键词
有向装配连接图
有向割集
递归收缩算法
-
Keywords
directed assembly connection graph
directed cutsets
recursive contraction algorithm
-
分类号
TP391.73
[自动化与计算机技术—计算机应用技术]
-
-
题名递归收缩算法中支点的处理策略研究
- 2
-
-
作者
梁勇强
-
机构
玉林师范学院数学与计算机科学系
-
出处
《计算机工程与应用》
CSCD
北大核心
2011年第19期54-59,共6页
-
基金
广西壮族自治区教育厅科研项目(No.200911LX353)
-
文摘
为了确保生成无向图割集的递归收缩算法的正确性和稳定性,对算法中种子顶点是支点的情形进行了分析,并采取了新的处理策略。分析了支点具有一个非可吸簇的情形,引进附加吸入的概念,修正了种子顶点的BFSO值取值规则,解决了现有算法可能遗漏割集的问题。针对支点没有非可吸簇的情形,给出了一个新的处理策略,解决了现有算法在某些特殊输入条件下效率不高的问题,在理论上分析了新处理策略的有效性,并做了相应的实验比较,理论分析和实验比较均表明:新的处理策略采用提高了递归收缩算法的稳定性。
-
关键词
图
割集
边收缩图
递归收缩算法
支点
-
Keywords
graph
cutset
edge contraction
recursive contraction algorithm
pivot vertex
-
分类号
TP301.6
[自动化与计算机技术—计算机系统结构]
-
-
题名混合图在无向图割集生成中的应用
- 3
-
-
作者
梁勇强
朱晓姝
谢妙
-
机构
玉林师范学院数学与计算机科学系
玉林师范学院职业技术学院
-
出处
《计算机工程与设计》
CSCD
北大核心
2010年第11期2648-2653,共6页
-
基金
广西自然科学青年基金项目(桂科青0832101)
-
文摘
为了进一步提高生成无向图割集的递归收缩算法的执行效率,将无向图转换为一类特殊的混合图,并将转换结果代替无向图输入递归收缩算法进行处理,修改了递归收缩算法中相应的算法步骤,使得改进算法可以更高效地生成无向图的割集。在理论上论证了改进算法的正确性,并通过理论分析和实验比较了改进算法和现有算法的时间复杂度和空间复杂度。理论分析结果和实验比较结果均表明改进算法明显比现有算法高效。
-
关键词
混合图
无向图
割集
边被收缩图
递归收缩算法
-
Keywords
hybrid graph
undirected graph
cutest
edge-contracted graph
recursive contraction algorithm
-
分类号
TP301.6
[自动化与计算机技术—计算机系统结构]
-
-
题名利用附加拆卸约束提高拆卸序列生成效率
- 4
-
-
作者
梁勇强
刘峰
隆峻
-
机构
玉林师范学院职业技术学院
玉林师范学院物理与信息科学系
-
出处
《玉林师范学院学报》
2008年第5期17-20,共4页
-
文摘
为提高基于割集的拆卸序列生成算法的效率,在引进递归收缩算法生成拆卸连接图的割集之后,分析了递归收缩算法的特点,然后应用产品的附加拆卸约束精简拆卸连接图,使得拆卸连接图的有效的拆卸割集的生成更高效.最后给出了一个实例说明本文方法的有效性.
-
关键词
附加拆卸约束
拆卸序列
割集
递归收缩算法
-
Keywords
additional disassembly constraints
disassembly sequence
cutset
recursive contraction algorithm
-
分类号
TB115
[理学—应用数学]
-