dominating sets

[Sufian Hameed]

Hi,

is there any function/code to find the dominating set for a graph.... ?

regards

sufian

[Dan Schult]

It should not be hard to implement a function that tests whether
a set is a dominating set. The code for node_boundary() looks
similar to that. It is in the algorithms/boundary.py module at the
bottom.
It finds the boundary of a set of nodes, but to do that it finds all
neighbors. Adding a check if that set is the set of nodes of G would
check for dominating (see code snippet below).

allnodes=set(G)
testset=set(n for n in nbunch1 if n in G)
nbrs=set()
for n in testset:
nbrs.update(G[n])
if nbrs - allnodes: # some nodes left--not dominating
return False
else:
return True

Of course all nodes are a dominating set of G
so I guess you mean a smallest dominating set or something like that.
Do you have a good algorithm for finding which sets to check?
Dan

> --
>
> You received this message because you are subscribed to the Google
> Groups "networkx-discuss" group.
> To post to this group, send email to networkx-
> dis...@googlegroups.com.
> To unsubscribe from this group, send email to networkx-discuss
> +unsub...@googlegroups.com.
> For more options, visit this group at http://groups.google.com/
> group/networkx-discuss?hl=en.