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

Abstract: 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.

Key words: threshold-minimum dominating set problem, mathematical property, upper and lower bound algorithm, backtracking algorithm with reduction