Algorithmic aspects of Roman domination in graphs
From MaRDI portal
Publication:2053064
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
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
