最小支配阈值集问题的降阶回溯算法  

A backtracking algorithm with reduction for the threshold-minimum dominating set problem

作　　者：储旭 宁爱兵[1] 胡开元 代苏玉 张惠珍[1] CHU Xu;NING Ai-bing;HU Kai-yuan;DAI Su-yu;ZHANG Hui-zhen(Business School,University of Shanghai for Science&Technology,Shanghai 200093,China)

机构地区：[1]上海理工大学管理学院,上海200093

出　　处：《计算机工程与科学》2024年第5期897-906,共10页Computer Engineering & Science

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

摘　　要：图论中的最小支配阈值集问题是组合优化中的一个NP-Hard问题,该问题是最小支配集问题的一个扩展问题。基于给定无向图G=(V,E)和阈值r的最小支配阈值集问题进行研究,首先得出一些可以降低问题规模的数学性质并证明,利用这些性质可以减小问题规模,降低问题的求解难度;然后设计出上界子算法、下界子算法和降阶子算法,并基于这些子算法提出了一种可以减小问题规模同时得到最优解的降阶回溯算法BAR;最后,通过一个示例分析和若干随机算例测试验证了降阶回溯算法可有效降低问题的求解难度。The threshold-minimum dominating set problem in graph theory is a NP-hard problem in combinatorial optimization,which is essentially an extension of the minimum dominant set problem.This paper studies the threshold-minimum dominating set problem for the given undirected graph G=(V,E)and threshold value r.Firstly,some mathematical properties and corresponding proof are studied,and these properties can be used to reduce the size of the given problem,thereby reducing the difficulty of the problem solving.Secondly,the upper and lower bound sub-algorithms and the reduced order sub-algorithm are designed.Based on these sub-algorithms,a backtracking algorithm with reduction(BAR)is proposed,which can reduce the problem size and get the optimal solution.Finally,an example analysis and some random examples verifies that the algorithm can effectively reduce the difficulty of problem-solving.

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

分 类 号：TP301.6[自动化与计算机技术—计算机系统结构]