On the computational complexity of Roman\(\{2\}\)-domination in grid graphs

DOI10.1007/s10878-023-01024-7zbMath1518.90119OpenAlexW4365518251MaRDI QIDQ6043333

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 complexitygrid graphsAPX-hardnessRoman\(\{2\}\)-domination

Mathematics Subject Classification ID

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

Cites Work

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

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