On the computational complexity of Roman\2\-domination in grid graphs

DOI10.1007/S10878-023-01024-7MaRDI QIDQ6043333zbMATH OpenOpenAlexFDO

Authors Aflatoun Amouzandeh, Ahmad Moradi

Publication date 5 May 2023

Published in Journal of Combinatorial Optimization (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/s10878-023-01024-7

zbMATH Keywords

computational complexityAPX-hardnessgrid graphsRoman\(\{2\}\)-domination

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Combinatorial optimization (90C27) Abstract computational complexity for mathematical programming problems (90C60)

Recommendations

• New complexity results on Roman {2}-domination
• Roman \(\{2 \}\)-domination
• Roman domination in subgraphs of grids
• Roman \(\{2\}\)-domination problem in graphs
• Complexity of Roman \(\{ 2 \} \)-domination and the double Roman domination in graphs

Cites work

• A simplified NP-complete MAXSAT problem
• APPROXIMATING POLYGONS AND SUBDIVISIONS WITH MINIMUM-LINK PATHS
• Complexity of Roman \(\{ 2 \} \)-domination and the double Roman domination in graphs
• Italian domination in trees
• Optimization, approximation, and complexity classes
• Roman \(\{2 \}\)-domination
• Roman \(\{2\}\)-bondage number of a graph
• Roman domination in subgraphs of grids
• Roman, Italian, and 2-domination
• Some simplified NP-complete graph problems
• Universality considerations in VLSI circuits

Cited in

(4)

• An explicit construction of optimal dominating and [1, 2]–dominating sets in grid
• Metaheuristic algorithms for solving Roman \(\{2\}\)-domination problem
• The 2-domination and Roman domination numbers of grid graphs
• New complexity results on Roman {2}-domination

This page was built for publication: On the computational complexity of Roman\(\{2\}\)-domination in grid graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6043333)