## 4 Malatya Dominating Set Algorithm (MDSA)
### The Main Algorithm
\(\square\)  
```
functionDominatingSet (A) output: \(\text{VD}\leftarrow\emptyset\) input: A, //Adjacency matrix
1 n \(\leftarrow\) sizeof(A) //\(n\) is the size of graph (\(G\) = (\(V\),\(E\)), \(|V|=n\))
2 MC1 \(\leftarrow\) 0, MC2 \(\leftarrow\) 0
3 NodeColor \(\leftarrow\) 0 //\(\text{Grey}\)\(\leftarrow\) 1, White nod \(e\) = 0
4 D \(\leftarrow\) \(\emptyset\) //Degree vector
5 DA \(\leftarrow\)\(\emptyset\) //Active degree vector
6 NodeColor(G) \(\leftarrow\) white
7 while Termination \(\
eq\) False
8 MC1 \(\leftarrow\) FirstMalayaCentrality (A, D, DA, MC1)
9 MC2 \(\leftarrow\) SecondMalatyaCentrality (A, D, DA, MC1, MC2)
10 NodeColor \(\leftarrow\) NodeSelection (A, D, DA, NodeColor, MC2)
11 Termination \(\leftarrow\) Terminate (A, NodeColor)
12 End
13 return VD
14 functionNodeSelection (A, D, DA, NodeColor, MC2, VD)
15 SN \(\leftarrow\) Max (MC2) //Select the node with the maximum MC2 value (white node has priority)
16 NodeColor (SN) \(\leftarrow\) red
17 NodeColor (Neighbors of SN) \(\leftarrow\) grey
18 return NodeColor
19 functionTerminate (A, NodeColor)
20 n \(\leftarrow\) sizeof (A)
21 Termination \(\leftarrow\) false;
22 for\(i\gets 1\), \(\ldots\), n
23 if NodeColor (i) is white
24 Termination \(\leftarrow\) true
25 end
26
27 end
28 returnTermination
```  
**Algorithm 3** The Dominating Set Algorithm  
Theorem 2: _Assume that \(G=(V,E)\) is a graph where \(|V|=n\) and \(|E|=m\). Algorithm 2 has polynomial time and space complexities._  
Proof: Proceeding analogously as in the proof of Theorem 1, similar results yield. \(\square\)  
Theorem 3: _Assume that \(G=(V,E)\) is a graph where \(|V|=n\) and \(|E|=m\). DominatingSet algorithm has polynomial time and space complexities._  
Proof: Assume that \(G=(V,E)\) and its adjacency matrix is A of size rxn. In the first step, \(\Psi_{1}(\ldots)\) and \(\Psi_{2}(\ldots)\) are computed. The arrays \(\Psi_{1}(\ldots)\) and \(\Psi_{2}(\ldots)\) are 1-dimensional arrays, and the searching process for selecting a node for the dominating set takes place and its time complexity is \(T_{S}(n)=O(n)\). After selecting one node for the dominating set this node is removed from the graph. After removing the selected node (\(u_{1}\)), the graph is updated, and so \(G_{1}=G-\{u_{1}\}\) where \(G_{1}=(V_{1},E_{1})\) where \(V_{1}\subset V\) and \(E_{1}\subset E\). For the second node selection process, Algorithms 1 and 2 are used to compute the centrality values of G1. Then, selecting the next node for the dominating set is a linear process, and the selected node (\(u_{2}\)) is also removed from the graph. Then the graph is updated again. \(G_{2}=G_{1}-\{u_{2}\}\) where \(G_{2}=(V_{2},E_{2})\) where \(V_{2}\subset V_{1}\) and \(E_{2}\subset E_{1}\). This process continues this way until \(G_{\gamma(G)}\) contains all grey nodes or null graphs where \(\gamma(G)\) is the domination number of graphs is the cardinality of the dominating set. So, the sequence of graph updating is:  
\(G_{1}=G-\{u_{1}\}\), where \(G_{1}=(V_{1},E_{1})\), where \(V_{1}\subset V\) and \(E_{1}\subset E\). \(G_{2}=G_{1}-\{u_{2}\}\), where \(G_{2}=(V_{2},E_{2})\) where \(V_{2}\subset V_{1}\) and \(E_{2}\subset E_{1}\). \(G_{3}=G_{2}-\{u_{3}\}\), where \(G_{3}=(V_{3},E_{3})\) where \(V_{3}\subset V_{2}\) and \(E_{3}\subset E_{2}\). \(\ldots\ldots\ldots\ldots\ldots\ldots\ldots\)  
\(G_{\gamma}(G)=G_{\gamma}(G)-1-\{u_{\gamma}(G)\}\) where \(G_{\gamma(G)}=\left(V_{\gamma(G)},E_{\gamma(G)}\right)\) where \(V_{\gamma(G)}\subset V_{\gamma(G)-1}\) and \(E_{\gamma(G)}\subset E_{\gamma(G)-1}\). The time complexity of dominating set algorithm is:  
Case 1: Adjacency matrix, and \(\gamma(G)\) is the cardinality of dominating set, \(T_{S}(\ldots)\) is the time searching node for dominating set.