Generate a Weakly Connected Dominating Set (WCDS) of a graph.
[Go,N,E] = NL_G_WCDS(G)
Graph.
List of master nodes (nucleus).
List of slave nodes (electron).
Output graph.
NL_G_WCDS performs the Weakly Connected Dominated Set (WCDS) of the graph G (WIKIPEDIA). Each node of the graph receives a role (master/slave, nucleus/electron). The list of master (respectivelly slave) nodes is N (respectivelly E). The most connected node of the graph is selected as the root. It is also a master node. Each node can be white, gray or black. All nodes are initialized to white, except the root node that is black. The list T is defined and updated with black and gray nodes. When a white or gray vertex is colored in black, all of its white neighbors become gray. When a vertex is colored in black, it is placed in T along with all of its newly grey neighbors. The construction runs while there is white nodes in the graph. At each loop, the candidates consist of the gray nodes of T and their adjacent white nodes. For each candidate, the number of white vertices that are in the direct neighborhood is performed. The candidate that has the maximum value is chosen to be dyed black.