Algorithmic complexity of outer independent Roman domination and outer independent total Roman domination

DOI10.1007/S10878-020-00682-1zbMath1468.05219OpenAlexW3115344122MaRDI QIDQ2025071

Abolfazl Poureidi, Mehrdad Ghaznavi, Jafar Fathali

Publication date: 11 May 2021

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

Full work available at URL: https://doi.org/10.1007/s10878-020-00682-1

zbMATH Keywords

NP-hard problemproper interval graphlinear algorithmouter independent Roman dominating functionouter independent total Roman dominating function

Mathematics Subject Classification ID

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

Related Items (2)

Outer independent Roman domination number of trees ⋮ Unnamed Item

Cites Work

• Unnamed Item
• Unnamed Item
• Secure domination in proper interval graphs
• Outer-independent total Roman domination in graphs
• New algorithms for weighted \(k\)-domination and total \(k\)-domination problems in proper interval graphs
• The eternal dominating set problem for proper interval graphs
• Optimal greedy algorithms for indifference graphs
• A linear time algorithm for liar's domination problem in proper interval graphs
• Defendens Imperium Romanum: A Classical Problem in Military Strategy
• Outer independent Roman dominating functions in graphs

This page was built for publication: Algorithmic complexity of outer independent Roman domination and outer independent total Roman domination