Computing the domination number of grid graphs
From MaRDI portal
Publication:553994
zbMath1222.05194MaRDI QIDQ553994
Anton Isopoussu, Simon Crevals, Samu Alanko, Ville H. Pettersson, Patric R. J. Östergård
Publication date: 29 July 2011
Published in: The Electronic Journal of Combinatorics (Search for Journal in Brave)
Full work available at URL: https://eudml.org/doc/232410
Dynamic programming (90C39) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)
Related Items (19)
A constant time algorithm for some optimization problems in rotagraphs and fasciagraphs ⋮ A New Distributed Algorithm for Computing a Dominating Set on Grids ⋮ Unnamed Item ⋮ Independent transversal domination in trees, products and under local changes to a graph ⋮ Non split hop domination number for some mirror graphs and Cartesian product of two distinct paths ⋮ Strong restrained domination number on trees and product of graphs: An algorithmic approach ⋮ Binary programming formulations for the upper domination problem ⋮ Thresholds for the monochromatic clique transversal game ⋮ Unnamed Item ⋮ Partial domination - the isolation number of a graph ⋮ On the advice complexity of the online dominating set problem ⋮ The domination complexity and related extremal values of large 3D torus ⋮ An explicit construction of optimal dominating and [1, 2–dominating sets in grid] ⋮ Number of dominating sets in cylindric square grid graphs ⋮ A general lower bound for the domination number of cylindrical graphs ⋮ The secure domination number of Cartesian products of small graphs with paths and cycles ⋮ Product throttling ⋮ Independent domination of grids ⋮ On \((t,r)\) broadcast domination numbers of grids
Uses Software
This page was built for publication: Computing the domination number of grid graphs
