New complexity results on Roman {2}-domination

DOI10.1051/RO/2023049MaRDI QIDQ6050641zbMATH OpenFDO

Authors V. Leoni

Publication date 19 September 2023

Published in RAIRO - Operations Research (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://doi.org/10.1051/RO/2023049

zbMATH Keywords

caterpillardecompositionefficient algorithmNP-complete

Mathematics Subject Classification ID

Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Graph algorithms (graph-theoretic aspects) (05C85) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Recommendations

• Roman \(\{2 \}\)-domination
• Roman \(\{2\}\)-domination problem in graphs
• Complexity of Roman \(\{ 2 \} \)-domination and the double Roman domination in graphs
• On the computational complexity of Roman\(\{2\}\)-domination in grid graphs
• Roman \(\{k\}\)-domination in trees and complexity results for some classes of graphs

Cited in

(7)

• Roman \(\{2\}\)-domination problem in graphs
• Roman \(\{2 \}\)-domination
• On the computational complexity of Roman\(\{2\}\)-domination in grid graphs
• Roman \([1,2]\)-domination of graphs
• m-eternal domination and variants on some classes of finite and infinite graphs
• Characterizations of Italian graphs and Sicilian graphs
• Hardness and algorithmic results for Roman \{3\}-domination

This page was built for publication: New complexity results on Roman {2}-domination

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