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

摘要：

为了确保生成无向图割集的递归收缩算法的正确性和稳定性,对算法中种子顶点是支点的情形进行了分析,并采取了新的处理策略.分析了支点具有一个非可吸簇的情形,引进附加吸入的概念,修正了种子顶点的BFSO值取值规则,解决了现有算法可能遗漏割集的问题.针对支点没有非可吸簇的情形,给出了一个新的处理策略,解决了现有算法在某些特殊输入条件下效率不高的问题,在理论上分析了新处理策略的有效性,并做了相应的实验比较,理论分析和实验比较均表明:新的处理策略采用提高了递归收缩算法的稳定性.

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

所属期刊栏目：47

分类号：TP301.6(计算技术、计算机技术)

资助基金：广西壮族自治区教育厅科研项目200911LX353

在线出版日期：2012-01-14（万方平台首次上网日期，不代表论文的发表时间）

页数：共6页

页码：54-59