Analysis of Dominating Subset with Minimal Weight Problem

Burak Ordin, Fidan Nuriyeva


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.


Combinatorial Optimization; NP-Complete in the strong sense; Dominating Subset with Minimal Weight Problem; Weighted Set Covering Problem; Set Covering Problem

Full Text: