An explicit construction of optimal dominating and [1, 2]–dominating sets in grid

DOI10.1016/j.akcej.2019.06.011zbMath1471.05086arXiv1707.06471OpenAlexW3042426200MaRDI QIDQ4956183

Mohsen Alambardar Meybodi, Pouyeh Sharifani, Mohammad Reza Hooshmandasl

Publication date: 1 September 2021

Published in: AKCE International Journal of Graphs and Combinatorics (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1707.06471

zbMATH Keywords

dynamic programmingNP-completenessdominating setgrid graph\([1, 2\)-dominating set]

Mathematics Subject Classification ID

Dynamic programming (90C39) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

Cites Work

• \([1,2\)-domination in graphs]
• Computing the domination number of grid graphs
• \([1,2\)-sets and \([1,2]\)-total sets in trees with algorithms]
• Connected minimum secure-dominating sets in grids
• Some notes on the isolate domination in graphs
• \([1,2\)-sets in graphs]
• On graphs with disjoint dominating and 2-dominating sets
• The Domination Number of Grids
• A New Distributed Algorithm for Computing a Dominating Set on Grids
• The NP-completeness column: an ongoing guide
• Planar Formulae and Their Uses
• Trees with equal 2-domination and 2-independence numbers
• Characterization of block graphs with equal 2-domination number and domination number plus one
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: An explicit construction of optimal dominating and [1, 2]–dominating sets in grid