Algorithmic aspects of Roman domination in graphs

DOI10.1007/S12190-020-01345-4zbMath1475.05137OpenAlexW3016425788MaRDI QIDQ2053064

Chakradhar Padamutham, Venkata Subba Reddy Palagiri

Publication date: 29 November 2021

Published in: Journal of Applied Mathematics and Computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s12190-020-01345-4

zbMATH Keywords

NP-completenessAPX-completeRoman dominationtree convex bipartite graph

Mathematics Subject Classification ID

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

Related Items (11)

Algorithmic aspects of total Roman and total double Roman domination in graphs ⋮ Algorithmic aspects of outer independent Roman domination in graphs ⋮ Unique response Roman domination: complexity and algorithms ⋮ Approximation algorithm for (connected) Italian dominating function ⋮ Roman \(k\)-domination: hardness, approximation and parameterized results ⋮ Complexity aspects of restrained Roman domination in graphs ⋮ Algorithmic results in Roman dominating functions on graphs ⋮ Independent roman $\{3\}$-domination ⋮ Double vertex-edge domination in graphs: complexity and algorithms ⋮ Nearly tight approximation algorithm for (connected) Roman dominating set ⋮ Algorithmic complexity of weakly connected Roman domination in graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Counting independent sets in tree convex bipartite graphs
• Efficient algorithms for Roman domination on some classes of graphs
• On the Roman domination number of a graph
• Optimization, approximation, and complexity classes
• Defending the Roman Empire from multiple attacks
• Roman domination in graphs.
• Some APX-completeness results for cubic graphs
• Defending the Roman Empire---a new strategy
• Threshold graphs and related topics
• The monadic second-order logic of graphs. I: Recognizable sets of finite graphs
• Defendens Imperium Romanum: A Classical Problem in Military Strategy
• A threshold of ln n for approximating set cover
• A characterization of Roman trees
• Node-and edge-deletion NP-complete problems
• Algorithms and Computation

This page was built for publication: Algorithmic aspects of Roman domination in graphs