Unique response Roman domination: complexity and algorithms

DOI10.1007/s00453-023-01171-7OpenAlexW4386414857MaRDI QIDQ6088304

Dinabandhu Pradhan, Juhi Chaudhary, Sumanta Banerjee

Publication date: 13 December 2023

Published in: Algorithmica (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00453-023-01171-7

zbMATH Keywords

NP-completenesspolynomial-time algorithmdominationRoman dominationunique response Roman dominationunique response Roman function

Mathematics Subject Classification ID

Algorithms in computer science (68Wxx) Graph theory (05Cxx)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Roman \(\{2 \}\)-domination
• Double Roman domination
• Italian domination in trees
• Dominating sets for split and bipartite graphs
• Completely separable graphs
• Efficient algorithms for Roman domination on some classes of graphs
• A linear time recognition algorithm for proper interval graphs
• Distance-hereditary graphs
• The NP-completeness of Steiner tree and dominating set for chordal bipartite graphs
• A unified approach to domination problems on interval graphs
• Weighted connected domination and Steiner trees in distance-hereditary graphs
• The algorithmic use of hypertree structure and maximum neighbourhood orderings
• Roman domination in graphs.
• A note on Roman domination of digraphs
• Perfect Roman domination in trees
• Double Roman domination in trees
• Perfect Italian domination in trees
• Paired-domination problem on distance-hereditary graphs
• Algorithmic aspects of Roman domination in graphs
• Algorithm and hardness results in double Roman domination of graphs
• Perfect Italian domination in graphs: complexity and algorithms
• Unique response Roman domination in graphs
• Outer independent double Roman domination
• Algorithmic results on double Roman domination in graphs
• Perfect Roman domination in graphs
• On the double Roman domination of graphs
• Signed Roman domination in graphs
• Roman dominating influence parameters
• Distance-hereditary graphs are clique-perfect
• Perfect Italian domination in cographs
• Homogeneous sets and domination: A linear time algorithm for distance?hereditary graphs
• Defendens Imperium Romanum: A Classical Problem in Military Strategy
• Outer independent Roman dominating functions in graphs
• Domination in permutation graphs
• Distance-Hereditary Graphs, Steiner Trees, and Connected Domination
• A Greedy Heuristic for the Set-Covering Problem
• Efficient Algorithms for the Domination Problems on Interval and Circular-Arc Graphs
• Graph Classes: A Survey
• Characterization of Efficiently Parallel Solvable Problems on Distance-Hereditary Graphs
• Complexity of Roman {2}-domination and the double Roman domination in graphs
• Analytical approach to parallel repetition
• The complexity of theorem-proving procedures

This page was built for publication: Unique response Roman domination: complexity and algorithms