论文研究图论中最大独立集问题的精确算法.pdf

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