dominate: Dominating Sets

In cccd: Class Cover Catch Digraphs

Dominating Sets

Description

find maximum dominating sets in (di)graphs.

Usage

dominate(g, method = "greedy",proportion=1.0)

Arguments

g	an adjacency matrix.
method	one of "greedy","random","byRadius", "greedyProportion".
proportion	proportion of points to cover.

Details

dominate is the main program which calls the others, as indicated by method. Greedy is the greedy dominating algorithm. In the greedy method ties are broken by first index (a la which.max). The byRadius method uses the radii to break ties while the random routine breaks ties randomly. If proportion is given, the algorithm stops after proportion points are covered.

Value

a vector of vertices corresponding to the dominating set.

Author(s)

David J. Marchette [e-mail]

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)
## Not run: 
plot(G,balls=TRUE,D=D)

## End(Not run)

cccd documentation built on April 8, 2022, 5:08 p.m.