Powers of large matrices on GPU platforms to compute the Roman domination number of cylindrical graphs

Abstract

The Roman domination in a graph $G$ is a variant of the classical domination, defined by means of a so-called Roman domination function $f:V(G)\to \{0,1,2\}$ such that if $f(v)=0$ then, the vertex $v$ is adjacent to at least one vertex $w$ with $f(w)=2$. The weight $f(G)$ of a Roman dominating function of $G$ is the sum of the weights of all vertices of $G$, that is, $f(G)={\sum }_{u\in V(G)}f(u)$. The Roman domination number ${\gamma }_R(G)$ is the minimum weight of a Roman dominating function of $G$. In this paper we propose algorithms to compute this parameter involving the $(\min ,+)$ powers of large matrices with high computational requirements and the GPU (Graphics Processing Unit) allows us to accelerate such operations. Specific routines have been developed to efficiently compute the $(\min ,+)$ product on GPU architecture, taking advantage of its computational power. These algorithms allow us to compute the Roman domination number of cylindrical graphs $P_m\square C_n$ i.e., the Cartesian product of a path and a cycle, in cases $m=7,8,9$, $n\ge 3$ and $m\ge$10$,n\equiv 0(\mathrm{mod}5)$. Moreover, we provide a lower bound for the remaining cases $m\ge 10,n\not\equiv 0(\mathrm{mod}5)$.

References in corpus (1)

• BTAS: A Library for Tropical Algebra

Cited by in corpus (2)

• The 2-domination number of cylindrical graphs
• HPC acceleration of large (min, +) matrix products to compute domination-type parameters in graphs