Idom.num.up.bnd {pcds}

Indicator for an upper bound for the domination number by the exact algorithm

Description

Returns 1 if the domination number is less than or equal to the prespecified value k and also the indices (i.e., row numbers) of a dominating set of size k based on the incidence matrix Inc.Mat of a graph or a digraph. 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

Idom.num.up.bnd(Inc.Mat, k)

Arguments

Inc.Mat

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

k

A positive integer for the upper bound (to be checked) for the domination number.

Value

A list with two elements

dom.up.bnd

The upper bound (to be checked) for the domination number. It is prespecified as k in the function arguments.

Idom.num.up.bnd

The indicator for the upper bound for domination number of the graph or digraph being the specified value k or not. It returns 1 if the upper bound is k, and 0 otherwise based on the incidence matrix Inc.Mat of the graph or digraph.

ind.dom.set

Indices of the rows in the incidence matrix Inc.Mat that correspond to the vertices in the dominating set of size k if it exists, otherwise it yields NULL.

Author(s)

Elvan Ceyhan

See Also

dom.num.exact and dom.num.greedy

Examples

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

dom.num.greedy(M)
Idom.num.up.bnd(M,2)

for (k in 1:n)
print(c(k,Idom.num.up.bnd(M,k)))