Powers of large matrices on GPU platforms to compute the Roman domination number of cylindrical graphs
<|reference_start|>Powers of large matrices on GPU platforms to compute the Roman domination number of cylindrical graphs: 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\colon 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\Box C_n$ i.e., the Cartesian product of a path and a cycle, in cases $m=7,8,9$, $ n\geq 3$ and $m\geq $10$, n\equiv 0\pmod 5$. Moreover, we provide a lower bound for the remaining cases $m\geq 10, n\not\equiv 0\pmod 5$.<|reference_end|>
@article{martínez2024powers,
    title={Powers of large matrices on GPU platforms to compute the Roman
  domination number of cylindrical graphs},
    author={J.A. Mart'inez, E.M. Garz'on and M.L. Puertas},
    journal={IEEE Access, vol. 9, pp. 29346-29355, 2021},
    year={2024},
    doi={10.1109/ACCESS.2021.3058738},
    archivePrefix={arXiv},
    eprint={2409.17658},
    primaryClass={math.CO cs.DM}
}