计算机工程与科学

作者：储旭, 宁爱兵, 胡开元, 代苏玉, 张惠珍

单位：上海理工大学管理学院，上海 200093

关键词：最小支配阈值集问题；数学性质；上下界算法；降阶回溯算法 ,,

基金：国家自然科学基金(71401106)

图论中的最小支配阈值集问题是组合优化中的一个NP-Hard问题，该问题是最小支配集问题的一个扩展问题。基于给定无向图G=(V,E)和阈值r的最小支配阈值集问题进行研究，首先得出一些可以降低问题规模的数学性质并证明，利用这些性质可以减小问题规模，降低问题的求解难度；然后设计出上界子算法、下界子算法和降阶子算法，并基于这些子算法提出了一种可以减小问题规模同时得到最优解的降阶回溯算法BAR；最后，通过一个示例分析和若干随机算例测试验证了降阶回溯算法可有效降低问题的求解难度。

来源：2024年第5期

《计算机工程与科学》期刊编辑部

查看计算机工程与科学杂志2024年第5期