cccd (version 1.00.05)

dominate: Dominating Sets

Description

find maximum dominating sets in (di)graphs.

Usage

dominate(g, method = "greedy", verbose = TRUE)
dominate.greedy(g, weight=NULL)
dominate.byR(g)
dominate.random.sample(g)

Arguments

g

an adjacency matrix.

method

one of "greedy","systematic","random","byR".

weight

weight vector.

verbose

logical. In the case of systematic, whether to print out information as it goes.

Value

• a vector of vertices corresponding to the dominating set. Note: just like the vertex labels in igraph, these are 0-based.

Details

dominate is the main program which calls the others, as indicated by method. Greedy is the greedy dominating algorithm. The weight vector is used to break ties: in the case of a tie the vertex with the largest weight is chosen. The "by radius" algorithm uses the vector R as the criterion in the greedy algorithm, rather than degree. The random routine simply uses a random weighting instead of weighting by R. The systematic routine computes a true minimum dominating set, but may take a long time as it is not optimized and uses brute force. It first computes a greedy dominating set to reduce the search, but that's all.

References

T.W. Haynes, S.T. Hedetniemi and P.J. Slater, Fundamentals of Domination in Graphs, Marcel Dekker, 1998,

Examples

x <- matrix(runif(100),ncol=2)
y <- matrix(runif(100,-2,2),ncol=2)
G <- cccd(x,y)
D <- dominate(G)
plotCCCD(G,balls=T,D=D)