Computing the domination number of grid graphs
The electronic journal of combinatorics, Tome 18 (2011) no. 1
Let $\gamma_{m,n}$ denote the size of a minimum dominating set in the $m \times n$ grid graph. For the square grid graph, exact values for $\gamma_{n,n}$ have earlier been published for $n \leq 19$. By using a dynamic programming algorithm, the values of $\gamma_{m,n}$ for $m,n \leq 29$ are here obtained. Minimum dominating sets for square grid graphs up to size $29 \times 29$ are depicted.
@article{10_37236_628,
author = {Samu Alanko and Simon Crevals and Anton Isopoussu and Patric \"Osterg\r{a}rd and Ville Pettersson},
title = {Computing the domination number of grid graphs},
journal = {The electronic journal of combinatorics},
year = {2011},
volume = {18},
number = {1},
doi = {10.37236/628},
zbl = {1222.05194},
url = {http://geodesic.mathdoc.fr/articles/10.37236/628/}
}
TY - JOUR AU - Samu Alanko AU - Simon Crevals AU - Anton Isopoussu AU - Patric Östergård AU - Ville Pettersson TI - Computing the domination number of grid graphs JO - The electronic journal of combinatorics PY - 2011 VL - 18 IS - 1 UR - http://geodesic.mathdoc.fr/articles/10.37236/628/ DO - 10.37236/628 ID - 10_37236_628 ER -
%0 Journal Article %A Samu Alanko %A Simon Crevals %A Anton Isopoussu %A Patric Östergård %A Ville Pettersson %T Computing the domination number of grid graphs %J The electronic journal of combinatorics %D 2011 %V 18 %N 1 %U http://geodesic.mathdoc.fr/articles/10.37236/628/ %R 10.37236/628 %F 10_37236_628
Samu Alanko; Simon Crevals; Anton Isopoussu; Patric Östergård; Ville Pettersson. Computing the domination number of grid graphs. The electronic journal of combinatorics, Tome 18 (2011) no. 1. doi: 10.37236/628
Cité par Sources :