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