递归收缩算法中支点的处理策略研究  

Research on strategies for disposal of pivot vertex in recursive contraction algorithm

作　　者：梁勇强[1] 

机构地区：[1]玉林师范学院数学与计算机科学系,广西玉林537000

出　　处：《计算机工程与应用》2011年第19期54-59,共6页Computer Engineering and Applications

基　　金：广西壮族自治区教育厅科研项目(No.200911LX353)

摘　　要：为了确保生成无向图割集的递归收缩算法的正确性和稳定性,对算法中种子顶点是支点的情形进行了分析,并采取了新的处理策略。分析了支点具有一个非可吸簇的情形,引进附加吸入的概念,修正了种子顶点的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.

关 键 词：图 割集 边收缩图 递归收缩算法 支点 

分 类 号：TP301.6[自动化与计算机技术—计算机系统结构]