论文研究-递归收缩算法中支点的处理策略研究.pdf下载

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