论文部分内容阅读
独立集问题是图论和组合数学中常见的NP-hard问题,在许多领域都有着重要的应用。分支降阶是目前广泛用于设计精确算法求解NP-hard问题的技术之一,主要通过快速降阶、分支及递归求解原问题及其子问题。针对图论中最大独立集问题设计了一个分支降阶算法,并通过增加快速降阶规则来降低算法的时间复杂度,最终通过分析得出一个时间复杂度为O（1.285-n）的精确算法,该算法在理论上得到了一般图的最大独立集的最优解。