Search

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 subalgorithm 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. [ABSTRACT FROM AUTHOR]

Copyright of Computer Engineering & Science / Jisuanji Gongcheng yu Kexue is the property of Computer Engineering & Science and its content may not be copied or emailed to multiple sites or posted to a listserv without the copyright holder's express written permission. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract. (Copyright applies to all Abstracts.)

Copyright of Computer Engineering & Science / Jisuanji Gongcheng yu Kexue is the property of Computer Engineering & Science and its content may not be copied or emailed to multiple sites or posted to a listserv without the copyright holder's express written permission. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract. (Copyright applies to all Abstracts.)