Idom.numCSup.bnd.tri {pcds}

Indicator for an upper bound for the domination number of Central Similarity Proximity Catch Digraph (CS-PCD) by the exact algorithm - one triangle case

Description

Returns I(domination number of CS-PCD is less than or equal to k) where the vertices of the CS-PCD are the data points Xp, that is, returns 1 if the domination number of CS-PCD is less than the prespecified value k, returns 0 otherwise. It also provides the vertices (i.e., data points) in a dominating set of size k of CS-PCD.

CS proximity region is constructed with respect to the triangle tri=T(A,B,C) with expansion parameter t>0 and edge regions are based on the center M=(m_1,m_2) in Cartesian coordinates or M=(\alpha,\beta,\gamma) in barycentric coordinates in the interior of tri; default is M=(1,1,1) i.e., the center of mass of tri.

Edges of tri, AB, BC, AC, are also labeled as 3, 1, and 2, respectively. Loops are allowed in the digraph.

See also (Ceyhan (2012)).

Caveat: It takes a long time for large number of vertices (i.e., large number of row numbers).

Usage

Idom.numCSup.bnd.tri(Xp, k, tri, t, M = c(1, 1, 1))

Arguments

Xp

A set of 2D points which constitute the vertices of CS-PCD.

k

A positive integer to be tested for an upper bound for the domination number of CS-PCDs.

tri

A 3 \times 2 matrix with each row representing a vertex of the triangle.

t

A positive real number which serves as the expansion parameter in CS proximity region in the triangle tri.

M

A 2D point in Cartesian coordinates or a 3D point in barycentric coordinates which serves as a center in the interior of the triangle tri; default is M=(1,1,1), i.e. the center of mass of tri.

Value

A list with two elements

domUB

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

Idom.num.up.bnd

The indicator for the upper bound for domination number of CS-PCD being the specified value k or not. It returns 1 if the upper bound is k, and 0 otherwise.

ind.domset

The vertices (i.e., data points) in the dominating set of size k if it exists, otherwise it is NULL.

Author(s)

Elvan Ceyhan

References

Ceyhan E (2012). “An investigation of new graph invariants related to the domination number of random proximity catch digraphs.” Methodology and Computing in Applied Probability, 14(2), 299-334.

See Also

Idom.numCSup.bnd.std.tri, Idom.num.up.bnd, Idom.numASup.bnd.tri, and dom.num.exact

Examples

A<-c(1,1); B<-c(2,0); C<-c(1.5,2);
Tr<-rbind(A,B,C);
n<-10

set.seed(1)
Xp<-runif.tri(n,Tr)$gen.points

M<-as.numeric(runif.tri(1,Tr)$g)  #try also M<-c(1.6,1.0)

t<-.5

Idom.numCSup.bnd.tri(Xp,1,Tr,t,M)

for (k in 1:n)
  print(c(k,Idom.numCSup.bnd.tri(Xp,k,Tr,t,M)))