A backtracking algorithm with reduction for the threshold-minimum dominating set problem
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 stud-ied,and these properties can be used to reduce the size of the given problem,thereby reducing the diffi-culty 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 pro-posed,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.
threshold-minimum dominating set problemmathematical propertyupper and lower bound algorithmbacktracking algorithm with reduction
万方数据
维普
