-
题名递归收缩算法中支点的处理策略研究
- 1
-
-
作者
梁勇强
-
机构
玉林师范学院数学与计算机科学系
-
出处
《计算机工程与应用》
CSCD
北大核心
2011年第19期54-59,共6页
-
基金
广西壮族自治区教育厅科研项目(No.200911LX353)
-
文摘
为了确保生成无向图割集的递归收缩算法的正确性和稳定性,对算法中种子顶点是支点的情形进行了分析,并采取了新的处理策略。分析了支点具有一个非可吸簇的情形,引进附加吸入的概念,修正了种子顶点的BFSO值取值规则,解决了现有算法可能遗漏割集的问题。针对支点没有非可吸簇的情形,给出了一个新的处理策略,解决了现有算法在某些特殊输入条件下效率不高的问题,在理论上分析了新处理策略的有效性,并做了相应的实验比较,理论分析和实验比较均表明:新的处理策略采用提高了递归收缩算法的稳定性。
-
关键词
图
割集
边收缩图
递归收缩算法
支点
-
Keywords
graph
cutset
edge contraction
recursive contraction algorithm
pivot vertex
-
分类号
TP301.6
[自动化与计算机技术—计算机系统结构]
-