Total 2-rainbow domination in graphs: complexity and algorithms

DOI10.1142/S0129054123500260MaRDI QIDQ6629672zbMATH OpenFDO

Authors Manjay Kumar, P. Venkata Subba Reddy

Publication date 30 October 2024

Published in International Journal of Foundations of Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1142/S0129054123500260

zbMATH Keywords

approximation algorithmAPX-completenessdominationgraph classesinteger linear programmingNP-completenesstotal 2-rainbow domination

Mathematics Subject Classification ID

Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Approximation algorithms (68W25) Linear programming (90C05) Integer programming (90C10)

Recommendations

• Total 2-rainbow domination numbers of trees
• Complexity of 2-rainbow total domination problem
• Algorithmic aspects of total Roman ${2}$-domination in graphs
• Algorithmic aspects of the independent 2-rainbow domination number and independent Roman \(\{2\}\)-domination number
• On the 2-rainbow domination in graphs

Cites work

• 2-rainbow domination in generalized petersen graphs \(P(n,3)\)
• 2-rainbow domination of generalized Petersen graphs P(n,2)
• Algorithm and Hardness Results for Outer-connected Dominating Set in Graphs
• Algorithmic aspects of \(b\)-disjunctive domination in graphs
• Algorithmic aspects of semitotal domination in graphs
• Algorithms and Computation
• Approximation hardness of dominating set problems in bounded degree graphs
• Bounds on the 2-rainbow domination number of graphs
• Counting independent sets in tree convex bipartite graphs
• Graph Classes: A Survey
• Graphs with large total 2-rainbow domination number
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 1095171 (Why is no real title available?)
• scientific article; zbMATH DE number 1095172 (Why is no real title available?)
• Node-and edge-deletion NP-complete problems
• Note on 2-rainbow domination and Roman domination in graphs
• On \(k\)-rainbow domination in regular graphs
• On 2-rainbow domination and roman domination in graphs
• On the 2-rainbow domination in graphs
• Optimization, approximation, and complexity classes
• Rainbow domination in graphs
• Rainbow domination on trees
• Roman domination in graphs.
• Some APX-completeness results for cubic graphs
• The monadic second-order logic of graphs. I: Recognizable sets of finite graphs
• Threshold graphs and related topics
• Total \(k\)-rainbow domination numbers in graphs
• Total 2-rainbow domination numbers of trees
• Unicyclic graphs with strong equality between the 2-rainbow domination and independent 2-rainbow domination numbers

Cited in

(1)

• Complexity of 2-rainbow total domination problem

This page was built for publication: Total 2-rainbow domination in graphs: complexity and algorithms

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