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) - {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) = Σu∈V(G) f (u). The Roman domination number γ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 Pm Cn i.e., the Cartesian product of a path and a cycle, in cases m = 7, 8,9 n ≥ 3 and m ≥10, n ≡ 0 (mod 5). Moreover, we provide a lower bound for the remaining cases m ≥10, n ≡6 0 (mod 5).

Keywords

• Cylindrical graphs
• GPU platforms
• (min,+) matrix multiplication
• Roman domination