dom.num.greedy {pcds}

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)). 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.num.greedy(Inc.Mat)

Arguments

Inc.Mat

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

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.dom.set

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).

Author(s)

Elvan Ceyhan

References

Chvatal V (1979). “A greedy heuristic for the set-covering problem.” Mathematics of Operations Research, 4(3), 233 — 235.

Examples

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

dom.num.greedy(M)