Complexity of Roman \ 2 \ -domination and the double Roman domination in graphs

DOI10.1016/J.AKCEJ.2020.01.005MaRDI QIDQ4956233zbMATH OpenOpenAlexFDO

Authors Chakradhar Padamutham, Venkata Subba Reddy Palagiri

Publication date 1 September 2021

Published in AKCE International Journal of Graphs and Combinatorics (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://doi.org/10.1016/j.akcej.2020.01.005

zbMATH Keywords

approximation algorithmdouble Roman dominationNP-completeRoman \(\{ 2 \} \)-dominationtree convex bipartite graphs

Mathematics Subject Classification ID

Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Analysis of algorithms and problem complexity (68Q25)

Recommendations

• Algorithmic aspects of Roman domination in graphs
• Algorithmic results on double Roman domination in graphs
• On the double Roman domination in graphs
• Some progress on the double Roman domination in graphs
• Roman \(\{2\}\)-domination problem in graphs

Cites work

• Counting independent sets in tree convex bipartite graphs
• Double Roman domination
• Double Roman domination number
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 854567 (Why is no real title available?)
• Introduction to algorithms.
• Node-and edge-deletion NP-complete problems
• On the double Roman domination in graphs
• Roman \(\{2 \}\)-domination
• Roman domination in graphs.
• The monadic second-order logic of graphs. I: Recognizable sets of finite graphs

Cited in

(26)

• Domination parameters with number 2: interrelations and algorithmic consequences
• Algorithmic aspects of Roman domination in graphs
• Roman \(\{2\}\)-domination problem in graphs
• On the watching number of graphs using discharging procedure
• On algorithmic complexity of double Roman domination
• Algorithmic results on double Roman domination in graphs
• Complexity aspects of variants of independent Roman domination in graphs
• Roman domination on strongly chordal graphs
• Complexity issues of perfect Roman domination in graphs
• Independent Roman \(\{3\}\)-domination
• Algorithmic aspects of Roman \(\{3\}\)-domination in graphs
• On the computational complexity of Roman\(\{2\}\)-domination in grid graphs
• New complexity results on Roman {2}-domination
• Unique response Roman domination: complexity and algorithms
• Algorithmic aspects of total Roman ${2}$-domination in graphs
• Short cycles dictate dichotomy status of the Steiner tree problem on bisplit graphs
• Double Roman domination in graphs: algorithmic complexity
• Metaheuristic algorithms for solving Roman \(\{2\}\)-domination problem
• Roman \(\{3\}\)-domination in graphs: complexity and algorithms
• Further results on the \([k]\)-Roman domination in graphs
• Solving the minimum-cost double Roman domination problem
• Complexity issues concerning the quadruple Roman domination problem in graphs
• Characterizations of Italian graphs and Sicilian graphs
• Exploring algorithmic solutions for the independent Roman domination problem in graphs
• Bisplit graphs -- a structural and algorithmic study
• Algorithmic aspects of total Roman and total double Roman domination in graphs

This page was built for publication: Complexity of Roman \(\{ 2 \} \)-domination and the double Roman domination in graphs

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