Minimum dominating set (MDS) and its matlab code

---

Preface

   Minimum dominating set also plays an important role in network routing design , Next, let's study together ~

---

One 、 What is the minimum dominating set ？

   The minimum dominating set , Full name $MinimalDominatingSet$, Referred to as $MDS$. For Graphs $G=(V,E)$ Come on , set up $V^{\prime }$ The picture is $G$ A dominating set of , For any vertex in the graph $u$, Or belong to a collection $V^{\prime }$, Or with $V^{\prime }$ The vertices in the are adjacent to each other . stay $V^{\prime }$ After removing any element from ,$V^{\prime }$ No longer a dominating set , Then dominating set $V^{\prime }$ Is a minimal dominating set . call $G$ The dominating set with the least number of vertices in all dominating sets is the minimum dominating set , The number of vertices in the minimum dominating set is called dominating number .

Two 、 Solution

1、 Greedy strategy

   First, choose a point as the root , Then traverse according to the depth first to get the traversal sequence , Greedy according to the reverse sequence of the obtained sequence ：
   For a point that neither belongs to nor is connected to a point in the dominating set , If his parent node does not belong to the dominating set , Add its parent node to the dominating set , At the same time, its neighbor nodes are also marked .

2、 Pseudo code

   First step : Traverse the whole tree with the root node depth first , Find the number of each point in the depth first traversal sequence and the parent node number of each point .
   The second step : Check each point in the reverse order of depth first traversal （ I understand it as checking in the order of degrees from big to small ）, If the current point does not belong to the dominating set and is not connected to the point of the dominating set , And its parent node does not belong to the dominating set , Add its parent node to the dominating set , The number of dominant concentration points plus 1, Mark current node , At the same time, its neighbor nodes are also marked .
   The above two parts are referenced from the following website , And revised it according to my own understanding ：

https://www.cnblogs.com/Kissheart/p/9939887.html

3、matlab Code

Radius=10;
D=[];    % Degrees （ The number of neighbor nodes of a node ）
Node_Num=120;  % Number of nodes 
pointer=[];    %flag by 1 Set of points for 
flag=zeros(1,Node_Num);    % Mark the number that has been selected 
A=zeros(Node_Num,Node_Num);    % Construct adjacency matrix 

% Calculation degree 
for i=1:Node_Num
    num=0;
    for j=1:Node_Num
        if i~=j
        if [x(i)-x(j)]^2+[y(i)-y(j)]^2<=Radius^2    % If i and J Nodes can be adjacent 
            num=num+1;   %i Degrees +1
            A(i,j)=1;    % Marked as 1, It means having a neighbor relationship 
            end  
        end
    end
    d(i)=num;
    D=[D,d(i)];% Calculation degree    % Degree relationship of all nodes 

% Generate the minimum dominating set 
for ss=1:Node_Num
    if flag(ss)==0
       max=D(ss);
       j=ss;
      for i=1:Node_Num
         if max<D[i]...
            &&flag(i)==0;
            max=D(i);
            j=i;    % Find the vertex with the largest degree in turn 
         end    
      end
      flag(j)=1;
      for k=1:Node_Num
          if A(j,k)==1
            flag(k)=2;   % The adjacent nodes are marked 2
          end
      end 
   end
end

   The above code is mainly referenced from the following website and has been commented and modified , It's been tested , It can be used .

https://blog.csdn.net/ccsss22/article/details/115865567

summary

   Finding the minimum dominating set can help us in The data transmission volume of some nodes is significantly larger than that of other nodes In the case of network routing design , The above knowledge is also summarized under my personal understanding and experiment , I hope you can learn some knowledge ~