Computing the Domination Number of Grid Graphs

作者：Alanko Samu^*; Crevals Simon; Isopoussu Anton; Ostergard Patric; Pettersson Ville

来源：Electronic Journal of Combinatorics, 2011, 18(1): P141.

Let gamma(m,n) denote the size of a minimum dominating set in the m x n grid graph. For the square grid graph, exact values for gamma(n,n) have earlier been published for n <= 19. By using a dynamic programming algorithm, the values of gamma(m,n) for m, n <= 29 are here obtained. Minimum dominating sets for square grid graphs up to size 29 x 29 are depicted.

• 出版日期2011-7-15