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

时间:2022-10-01 23:12:21
【文件属性】:

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

文件大小:459KB

文件格式:PDF

更新时间:2022-10-01 23:12:21

论文研究

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


网友评论