## 5 Experimental Evaluation
### Results and Discussion  
Table 1 reports on the performance comparison of GH-MWDDS (without the optional reduction procedure) and LS, FD, VD, and CPLEX. The first two columns indicate the problem instance type. More specifically, the number of nodes (\(n\)) is provided in the first column, whereas the average degree (\(d\)) is shown in the second column. Obviously, the higher \(d\), the more dense is the network. Remember that for each combination of \(n\) and \(d\)--that is, for each table row--there are 20 randomly generated problem instances. The values shown in the tables represent the average results obtained for these 20 instances per table row. Table columns 3 and 4 contain the results of CPLEX. While the first one of these columns indicates the average solution quality obtained, the second column provides the average gap (in percent) between the found results and the upper bounds. The results of the other algorithms are provided in two columns for each algorithm. These columns report on the average solution quality (Value) and the average computation time (Time(s)) in seconds. Moreover, the 11-th column of the table indicates the average size of solutions (\(|DP|\)) in terms of the average number of disjoint dominating sets. Since the three algorithms LS, FD and VD start with the same greedy solution as initial solution, and the number of disjoint dominating sets does not change during local search, the column with heading \(|DP|\) holds for all three algorithms. Finally, in the last column of the table, the average size of the solutions of GH-MWDDS is given. In addition to evaluating GH-MWDDS, we also tested the following two additional versions. Henceforth we refer to the version of GH-MWDDS that removes redundant nodes in line 22 as GH-MWDDS\({}^{+}\). In addition, the algorithm can be easily adapted in order to solve the maximum disjoint dominating sets (MDDS) problem, instead of the MWDDS. The resulting greedy algorithm, which is called GH-MDDS, is obtained by replacing the \(score(\cdot)\) function in line 12 of Algorithm 1 by the \(white\_degree(\cdot)\) function of Equation (14). The experiential results obtained with GH-MDDS and GH-MWDDS\({}^{+}\) are provided in Table 2, whose structure is very similar to the one of Table 1.  
From the results displayed in Tables 1 and 2, the following observations can me made:  
* First of all, the ILP model (solved by CPLEX) is only useful in the context of the smallest problem instances. In fact, CPLEX obtains the best results for all networks with 50 nodes. As an additional information we can say that CPLEX was able to solve 8 out of 20 problem instances with 50 nodes and an average degree of 15 to optimality. Figure 2 exemplary shows the optimal solution obtained by CPLEX for network number 14 of those networks with 50 nodes and an average node degree of 15. Note that the nodes are divided into six dominating sets (as indicated by the colors of the nodes). The nodes which are colored in green are not assigned to any dominating set. * CPLEX already starts to fail for the instances with 100 nodes, for which the results are already inferior to those of GH-MWDDS. In fact, for most of the problem instances (starting from 150 nodes and an average degree of 60) CPLEX is unable to find anything but the trivial solution that contains no dominating set. * Concerning GH-MWDDS, we can observe that it dominates the three competitors from the literature for all problem instances in terms of solution quality as well as computational time. It is significantly better than the best of the other three approaches, while requiring a computation time that is approximately five orders of magnitude smaller than the time needed by the other methods. The improvement ratio of our algorithm with respect to VD (the best approach from the literature) is about 5.37. As expected, most solutions suffer from the existence of redundant nodes.