<< NARVAL_W_NucleusGWCDS NARVAL

NARVAL >> NARVAL > NARVAL_W_WCDS

NARVAL_W_WCDS

Generate the Weakly Connected Dominating Set (WCDS) of a graph.

Calling Sequence

[go,n,e] = NARVAL_W_WCDS(g)

Parameters

g :

graph.

n :

list of master nodes (nucleus).

e :

list of slave nodes (electron).

go :

output graph.

Description

NARVAL_W_WCDS performs the Weakly Connected Dominated Set (WCDS) go 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 a 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.

Examples

n=200;//network size
l=1000;//network squared area side
d=100;//Locality radius
[g]=NARVAL_T_LocalityConnex(n,l,d);//generation of a topology
[go,n,e]=NARVAL_W_WCDS(g);//application of NARVAL_W_WCDS
w=1;//window index
f=NARVAL_G_ShowNodesIndex(go,w);//graph visualization
n(1:10)//first ten nucleus
e(1:10)//first ten electrons

Dependency

NARVAL_G_GraphDegDistWD, NARVAL_G_NodeNeighbors

Authors

Foued Melakessou

Contact

Dr. Foued Melakessou

Research Associate

Interdisciplinary Centre for Security, Reliability and Trust

Room F106

University of Luxembourg

6, rue Coudenhove Kalergi

L-1359 Luxembourg-Kirchberg

E-mail: foued.melakessou@uni.lu

Tel: (+352) 46 66 44 5346

Home Page


<< NARVAL_W_NucleusGWCDS NARVAL