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

DOI10.1007/S10878-023-01024-7zbMATH Open1518.90119OpenAlexW4365518251MaRDI QIDQ6043333FDOQ6043333

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

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

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)

Cites Work

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

Cited In (2)

• An explicit construction of optimal dominating and [1, 2]–dominating sets in grid
• 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)