dom.greedy: Approximate domination number and approximate dominating set by the greedy algorithm

Description

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 (chvatal: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.

Usage

dom.greedy(Inc.Mat)

Value

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 Inc.Mat is given as input.
ind.domset: Indices of the rows in the incidence matrix Inc.Mat for the ((approximate) minimum dominating set). The row numbers in the incidence matrix correspond to the indices of the vertices (i.e., indices of the data points).

Arguments

Inc.Mat: A square matrix consisting of 0's and 1's which represents the incidence matrix of a graph or digraph.

Author

Elvan Ceyhan

References

Examples

Run this code

n<-5
M<-matrix(sample(c(0,1),n^2,replace=TRUE),nrow=n)
diag(M)<-1

dom.greedy(M)

Run the code above in your browser using DataLab