## 5 Experimental Evaluation
### Results and Discussion
As a result, GH-MWDDS\({}^{+}\) is able to produce solutions whose size (in terms of the number of disjoint dominating sets) is increased with respect to the solutions produced by GH-MWDDS. This is achieved without compromising the quality of the generated solutions. On the contrary, the quality of the obtained solutions is slightly improved, at the cost of a negligible amount of computation time. * In addition, from Table 2 we can observe that GH-MDDS and GH-MWDDS\({}^{+}\) achieve an overall average solution quality (see that last row of Table 2) of 3.667 and 9.515, respectively, and an average solution size (in terms of the number of disjoint dominating sets) of 24.089 and 21.541, respectively. It is worthwhile to note that GH-MDDS always produces solutions with the maximum possible size (equal to \(\delta(G)+1\)). However, the quality of these solutions (as measured by the objective function of the MWDDS problem) is, of course, lower than the quality of the solutions produced by GH-MWDDS. This is because GH-MDDS is primarily focused on finding solutions of large size, without taking into consideration the problem-specific knowledge of the lifetime values of the nodes. Therefore, a solution to the MWDDS problem with the maximum size does not necessarily correspond to the best MWDDS-solution. For example, in the case where \(n=250\) and \(d=140\), for which GA-MDDS finds a solution with an average value 9.584 and an average size 53.6, GH-MWDDS\({}^{+}\) finds solutions with an average value 22.514 and average size 47.7. * From above observations we can say that the poor performance of the three local search algorithms proposed by [PERSON] et al. [23] is mainly due to greedy heuristic used for producing the initial solutions for their local search approaches. Since this greedy heuristic was developed for the MDDS problem, and the local search approaches try to improve these solutions by making swaps among nodes of different disjoint dominating sets, they are limited to the size of the solutions found by the initial greedy heuristic, which cannot be changed later. As can be seen by our results, this way of proceeding limits too much the possibility of the local search algorithms to find improvements. In summary we can say that our GH-MWDDS approach is clearly a new state-of-the-art method for the MWDDS problem. In order to study the scalability of our approach, we finally generated two large-scale random geometric graphs with 10,000 nodes. Both graphs were generated by scattering 10,000 nodes randomly in the unit square, and connecting each pair of nodes whose geometric distance is below \(r=0.02\) (first graph), respectively \(r=0.03\) (second graph). The first graph has 61,646 edges, while the second one has 137,317 edges. The computation time of GH-MWDDS was 1.829 seconds for the first graph and 5.054 seconds for the second graph. This difference in computation time between the first and the second graph is due to the different density, which leads to a solution with two dominating sets in the case of the first graph and a solution with six dominating sets in the case of the second graph. The important point, however, is that the computation time of our algorithm is still very low, even in the context of large-scale graphs. The solutions of GH-MWDDS are graphically shown in Figure 3. Note that, in the case of the first graph, red and green nodes form dominating sets, while all but the pink-colored nodes in the case of the second graph are assigned to six different dominating sets. Figure 2: An optimal solution for network number 14 with 50 nodes and an average node degree of 15. The solution was produced by CPLEX. The color of the nodes indicates to which of six dominating sets they belong: Blue, dark blue, dark green, red, purple, and brown. The nodes colored in green do not belong to any dominating set.