View source: R/AuxDomination.R
dom.num.greedy | R Documentation |
Returns the (approximate) domination number
and the indices (i.e., row numbers) for the corresponding
(approximate) minimum dominating set
based on the incidence matrix Inc.Mat
of a graph or a digraph
by using the greedy algorithm (\insertCitechvatal:1979;textualpcds).
Here the row number in the incidence matrix corresponds
to the index of the vertex (i.e., index of the
data point). The function works
whether loops are allowed or not (i.e., whether the first diagonal
is all 1 or all 0).
This function may yield the actual domination number
or overestimates it.
dom.num.greedy(Inc.Mat)
Inc.Mat |
A square matrix consisting of 0's and 1's which represents the incidence matrix of a graph or digraph. |
A list
with two elements
dom.num |
The cardinality of the (approximate) minimum dominating set
found by the greedy algorithm.
i.e., (approximate) domination number of the graph or digraph
whose incidence matrix |
ind.dom.set |
Indices of the rows
in the incidence matrix |
Elvan Ceyhan
n<-5
M<-matrix(sample(c(0,1),n^2,replace=TRUE),nrow=n)
diag(M)<-1
dom.num.greedy(M)
Add the following code to your website.
For more information on customizing the embed code, read Embedding Snippets.