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

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