## 1 Introduction
Throughout this paper, we refer to the domatic partition problem as maximum disjoint dominating sets (MDDS) problem. The MDDS problem, which belongs to the large and important family of dominating set problems [14; 15; 16], is known to be NP-hard for general graphs [17]. [PERSON] et al. [18] proved the NP-completeness of one of its variants known as the 3-disjoint dominating sets problem that asks for deciding whether or not a given graph contains three disjoint dominating sets. The same authors showed that, unless P = NP, the MDDS problem has no polynomial-time approximation with a performance guarantee of less than 1.5. They also introduced a heuristic approach based on graph coloring. In the same year, [PERSON] et al. [19] proved that every graph of order \(n\) with maximum degree \(\Delta\) and minimum degree \(\delta\) includes a domatic partition (a collection of disjoint dominating sets) of size \((1-o(1))(\delta+1)/\ln\Delta\). Here, the term \(o(1)\) tends to zero as \(n\) increases. Moreover, they showed that there is no approximation algorithm for the MDDS problem with an approximation ratio of \((1+o(1))\ln n\) unless \(NP\subseteq DTIME(n^{(0\log\log n)})\). The same authors also provided a centralized algorithm to find a domatic partition of size \(\Omega(\delta/\ln\Delta)\). Based on this later work, [PERSON] and [PERSON] [20] defined the MDDS problem as the maximum cluster-lifetime problem and introduced a randomized, distributed algorithm that has--with high probability--a performance ratio of \(O(\log(n))\). [PERSON] and [PERSON] [21] demonstrated that the 3-disjoint dominating sets problem remains NP-complete even for planar unit disk graphs and studied the performance comparison of four greedy heuristics for the MDDS problem. In [22], a greedy heuristic of time complexity \(O(n^{3})\) is described. More recently, [PERSON] et al. [23] focused on a weighted variant of the MDDS problem which is henceforth labelled the maximum weighted disjoint Dominating Sets (MWDDS) problem. In this problem, each node of the input graph--corresponding to a deployed sensor device--carries a weight that corresponds to its remaining lifetime. The lifetime of a dominating set is then defined as the minimum of the lifetimes of the nodes that form part of the set. The optimization goal of the MWDDS is to find a domatic partition such that the sum of the lifetimes of the corresponding dominating sets is maximized. [PERSON] et al. devised three local search algorithms for the MWDDS problem. Each local search algorithm is a greedy heuristic of time complexity \(O(n^{3})\). The algorithm is based on the maximum weighted minimum of the lifetimes of the nodes that form part of the set. search algorithm is seeded with an initial feasible solution generated by a modified greedy heuristic from [22] and iteratively swaps nodes between different dominating sets in the solution, in the hope to increase the total lifetime of the network. These local search approaches differ in the way they realize the swaps. The main contributions of this paper can be summarized as follows:  
* We introduce an integer linear programming (ILP) model for the MWDDS problem. * We propose an efficient greedy heuristic for the MWDDS problem. * We conduct comprehensive experiments on a set of 640 problem instances in order to investigate the performance and the advantages of our greedy heuristic in comparison to the application of CPLEX and to recent state-of-the-art methods. The rest of this paper is organized as follows. In Section 2 we provide a technical description of the MWDDS problem and recall some required notations and basic definitions. Next, an ILP model for the MWDDS problem is presented in Section 3. In Section 4, we introduce a new greedy algorithm. Finally, in Section 5 we present and discuss the experimental results, while Section 6 summarizes the work and offers directions for future work.