Analysis of Dominating Subset with Minimal Weight Problem

The paper deals with the analysis of the combinatorial problem "dominating subset with minimal weight" problem that is equivalent to a subproblem in the cutting angle method which has been developed for solving a broad class of global optimization problems. An example is given for a more clear expression of the problem and its presentation is supported by simple graph notation. Then the complexity of the problem is discussed. It is proven that the problem is strongly NP-Complete by using the weighted set covering problem. Finally analysis of dominating subset with minimal weight problem is expressed for problems in small dimensions.