摘要
为了确保生成无向图割集的递归收缩算法的正确性和稳定性,对算法中种子顶点是支点的情形进行了分析,并采取了新的处理策略。分析了支点具有一个非可吸簇的情形,引进附加吸入的概念,修正了种子顶点的BFSO值取值规则,解决了现有算法可能遗漏割集的问题。针对支点没有非可吸簇的情形,给出了一个新的处理策略,解决了现有算法在某些特殊输入条件下效率不高的问题,在理论上分析了新处理策略的有效性,并做了相应的实验比较,理论分析和实验比较均表明:新的处理策略采用提高了递归收缩算法的稳定性。
To ensure the correctness and stability of the recursive contraction algorithm,which for generating all cutsets of a given undirected graph,the pivot cases of seed vertices are analyzed,and new disposal strategies are adopted.Firstly this paper analyzes pivot vertices which have only one inabsorbable cluster,introduces the notion of incidental absorption,corrected the rules of the setting of Breadth First Search（BFS） ordering of seed vertex,so as to solve the problem of the omission of cutset in the existing algorithm.And then,a new disposal strategy is adopted for the pivot vertices which have no inabsorbable cluster,so as to solve the problem of the inefficiency of the existing algorithm under some special circumstances of inputs.The validity of this new disposal strategy is theoretically analyzed,and the experimental comparisons are made.The re- sults of theoretical analysis and experimental comparisons show that the adoption of the new disposal strategy improves the stability of the recursive contraction algorithm.
出处
《计算机工程与应用》
CSCD
北大核心
2011年第19期54-59,共6页
Computer Engineering and Applications
基金
广西壮族自治区教育厅科研项目(No.200911LX353)
关键词
图
割集
边收缩图
递归收缩算法
支点
graph
cutset
edge contraction
recursive contraction algorithm
pivot vertex
