An experimental comparison of greedy heuristics for the minimum weight dominating set problem

Abstract

In this study, we deal with one of the fundamental problems in graph theory and combinatorial optimization, that is, the minimum weight dominating set problem (MWDS). We make a comparison between well-known greedy heuristics for the MWDS problem and we add two new modified greedy heuristics. Experimental results show that the latters are more effective and perform better that the other greedy heuristics.