## 4 Proposed Greedy Heuristic  
Greedy algorithms are constructive heuristics for building feasible solutions to combinatorial optimization problems. They start from an empty solution and iteratively add the most favorable component from a set of feasible extensions of the current partial solution until a complete solution is reached. That is, the component to be added at each construction step is chosen deterministically according to some greedy function, which is a measure for the goodness of the solution components. In general, greedy heuristics do not require overly large computation times. The main drawback of a greedy heuristic is that the single constructed solution is most likely not optimal. The pseudo-code of our greedy algorithm, henceforth labelled GH-MWDDS, is presented in Algorithm 1. Note that our greedy algorithm is a centralized algorithm whichmust be executed on a central unit that has the knowledge about the topology of the network and about the lifetime values of the individual nodes. At the start of the algorithm, the following sets are initialized. Solution \(\mathcal{D}\) is initialized to the empty set. Furthermore, set \(V_{\text{rem}}\), which contains all nodes that may still be added to a dominating set, is initialized to \(V\). Finally, set \(V_{\text{done}}\), which collects all nodes that already form part of a dominating set in \(\mathcal{D}\), is initialized to the empty set. Counter \(k\) counts the number of dominating sets that are being constructed. It is initialized to zero. At each main iteration \(k\geq 1\), the algorithm generates a dominating set \(D_{k}\) consisting of nodes from set \(V_{\text{rem}}\) which, as mentioned above, contains all nodes of \(G\) that do not form part of any of the already generated dominating sets \(D_{i}\), \(i=1,\ldots,k-1\); see lines 5 and 21. The algorithm stops once no further dominating set can be generated from the nodes in \(V_{\text{rem}}\). This is the case if at least one node \(v\in V\) and all its neighbors form part of \(V_{\text{done}}\). More formally, the algorithm stops if there is at least one \(v\in V\) such that \(N[v]\) is a subset of \(V_{\text{done}}\) (see line 5). ```
0: a simple, node-weighted, undirected graph \(G=(V,E,\text{lifetime})\)
0: a family of disjoint dominating sets \(\mathcal{D}=\{D_{1},D_{2},\cdots,D_{k}\}\)
1:\(\mathcal{D}\leftarrow\emptyset\)
2:\(k\gets 0\)
3:\(V_{\text{rem}}\gets V\)
4:\(V_{\text{done}}\leftarrow\emptyset\)
5:while not exists \(v\in V\) s.t. \(N[v]\) is a subset of \(V_{\text{done}}\)do
6:\(k\gets k+1\)
7:for each node \(v\in V\)do
8:\(color(v)\leftarrow\) WHITE
9:endfor
10:\(D_{k}\leftarrow\emptyset\)
11:while\(D_{k}\) is not a dominating set of \(G\) (that is, \(N[D_{k}]\
eq V\)) do
12:\(v^{*}\leftarrow\text{argmax}\{score(v)\mid v\in\{\mathcal{G}(D_{k})\cup\mathcal{ W}(D_{k})\}\cap V_{\text{rem}}\}\)
13:\(D_{k}\gets D_{k}\cup\{v^{*}\}\)
14:\(V_{\text{rem}}\gets V_{\text{rem}}\setminus\{v^{*}\}\)
15:for each node \(u\in N(v^{*})\)do
16:if (\(color(u)=\) WHITE ) then
17:\(color(v)\leftarrow\) GRAY
18:endif
19:endfor
20:\(color(v^{*})\leftarrow\) BLACK
21:endwhile
22:Reduce(\(D_{k}\), \(V_{\text{rem}}\), \(V_{\text{done}}\)) [optional]
23:\(\mathcal{D}\leftarrow\mathcal{D}\cup\{D_{k}\}\)
24:\(V_{\text{done}}\gets V_{\text{done}}\cup D_{k}\)
25:endwhile
26:return\(\mathcal{D}=\{D_{1},D_{2},\cdots,D_{k}\}\). ```  
**Algorithm 1** GH-MWDDS: A Greedy heuristic for the MWDDS problem  
The construction of a dominating set \(D_{k}\) at round \(k\) of the algorithm is done as follows. First, \(D_{k}\) is initialized to the empty set. At each moment, each node of the input graph \(G\) belongs to one of the following sets:  
* Black nodes: Nodes that are part of \(D_{k}\). * Gray nodes: Nodes in \(\mathcal{G}(D_{k}):=N(D_{k})\setminus D_{k}\), that is, nodes that are not contained in \(D_{k}\) but that are adjacent to at least one black node. * White nodes: Nodes in \(\mathcal{W}(D_{k}):=V\setminus N[D_{k}]\), that is, nodes that are neither gray nor black.