pcds (version 0.1.2)

dom.exact: Exact domination number (i.e., domination number by the exact algorithm)

Description

Returns the (exact) domination number based on the incidence matrix Inc.Mat of a graph or a digraph and the indices (i.e., row numbers of Inc.Mat) for the corresponding (exact) minimum dominating set. 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). It takes a rather long time for large number of vertices (i.e., large number of row numbers).

Usage

dom.exact(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 (exact) minimum dominating set i.e., (exact) domination number of the graph or digraph whose incidence matrix Inc.Mat is given as input.

ind.mds

Indices of the rows in the incidence matrix Inc.Mat for the (exact) minimum dominating set. The row numbers in the incidence matrix correspond to the indices of the vertices (i.e., indices of the data points).

See Also

dom.greedy, PEdom1D, PEdomtri, PEdomMTnd, and IndCSdomUBtri

Examples

# NOT RUN {
n<-10
M<-matrix(sample(c(0,1),n^2,replace=TRUE),nrow=n)
diag(M)<-1

dom.greedy(M)
IndUBdom(M,2)
dom.exact(M)

# }