Computing the domination number of grid graphs
From MaRDI portal
Summary: 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 \leqslant 19\). By using a dynamic programming algorithm, the values of \(\gamma _{m,n}\) for \(m,\, n\leqslant 29\) are here obtained. Minimum dominating sets for square grid graphs up to size \(29 \times 29\) are depicted.
Recommendations
Cited in
(45)- The domination complexity and related extremal values of large 3D torus
- On the advice complexity of the online dominating set problem
- Number of dominating sets in cylindric square grid graphs
- The secure domination number of Cartesian products of small graphs with paths and cycles
- Product throttling
- Independent transversal domination in trees, products and under local changes to a graph
- A general lower bound for the domination number of cylindrical graphs
- Independent domination of grids
- On \((t,r)\) broadcast domination numbers of grids
- Non split hop domination number for some mirror graphs and Cartesian product of two distinct paths
- A note on power domination in grid graphs
- Thresholds for the monochromatic clique transversal game
- Saturated domino coverings
- A constant time algorithm for some optimization problems in rotagraphs and fasciagraphs
- A new distributed algorithm for computing a dominating set on grids
- Domination of graphs in \(\mathbf{Z}^{n}_{p}\) and in \(\mathbf{Z}^{n}_{3} \times \mathbf{Z}^{m}_{2}\)
- scientific article; zbMATH DE number 4039319 (Why is no real title available?)
- scientific article; zbMATH DE number 4053037 (Why is no real title available?)
- scientific article; zbMATH DE number 4057564 (Why is no real title available?)
- scientific article; zbMATH DE number 139923 (Why is no real title available?)
- scientific article; zbMATH DE number 637533 (Why is no real title available?)
- scientific article; zbMATH DE number 734463 (Why is no real title available?)
- scientific article; zbMATH DE number 1990832 (Why is no real title available?)
- The domination numbers of the 5 × n and 6 × n grid graphs
- scientific article; zbMATH DE number 2114690 (Why is no real title available?)
- scientific article; zbMATH DE number 861433 (Why is no real title available?)
- An explicit construction of optimal dominating and [1, 2]–dominating sets in grid
- Total domination of grid graphs
- scientific article; zbMATH DE number 7583648 (Why is no real title available?)
- Independent [1,2]-domination of grids via min-plus algebra
- Partial domination -- the isolation number of a graph
- Split domination of Cartesian product graphs
- The 2-domination and Roman domination numbers of grid graphs
- scientific article; zbMATH DE number 5238980 (Why is no real title available?)
- scientific article; zbMATH DE number 7666852 (Why is no real title available?)
- Strong restrained domination number on trees and product of graphs: An algorithmic approach
- Binary programming formulations for the upper domination problem
- Learn to solve dominating set problem with GNN and reinforcement learning
- Variants of the domination number for flower snarks
- Efficient domination in grid graphs
- Domination polynomials of the grid, the cylinder, the torus, and the king graph
- Detour domination number of generalized mesh networks
- 1,2-efficiency in grid graphs
- Enumeration of 2-factored dominating sets in fixed-width grid graphs
- Grid graphs, Gorenstein polytopes, and domino stackings
This page was built for publication: Computing the domination number of grid graphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q553994)
