Hardness results of global Roman domination in graphs

DOI10.1016/J.DAM.2023.08.020zbMATH Open1526.05110OpenAlexW4386514390MaRDI QIDQ6069177FDOQ6069177

Authors: B. S. Panda, Pooja Goyal 

Publication date: 13 November 2023

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.dam.2023.08.020

Recommendations

• Algorithmic aspects of Roman domination in graphs
• Global Roman domination in graphs
• Roman \(\{3\}\)-domination in graphs: complexity and algorithms
• Global Roman domination in trees
• Algorithmic and complexity aspects of problems related to total Roman domination for graphs

zbMATH Keywords

NP-completenessdominationAPX-completeness

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Nonnumerical algorithms (68W05) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

Cites Work

• Introduction to algorithms.
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Some APX-completeness results for cubic graphs
• Roman domination in graphs.
• Threshold graphs and related topics
• Incidence matrices and interval graphs
• Title not available (Why is that?)
• Title not available (Why is that?)
• Roman domination on strongly chordal graphs
• Global Roman domination in trees
• Hardness results of global Roman domination in graphs
• Global Roman domination in graphs

Cited In (3)

• Hardness results of global Roman domination in graphs
• Global Roman domination in graphs
• Approximation algorithm for the minimum partial connected Roman dominating set problem

This page was built for publication: Hardness results of global Roman domination in graphs

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