Algorithmic complexity of weakly connected Roman domination in graphs

DOI10.1142/S1793830921501251zbMath1487.05193OpenAlexW3149723690MaRDI QIDQ5866025

Khandelwal Himanshu, Padamutham Chakradhar, Palagiri Venkata Subba Reddy

Publication date: 10 June 2022

Published in: Discrete Mathematics, Algorithms and Applications (Search for Journal in Brave)

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

zbMATH Keywords

integer linear programming\(NP\)-completenessRoman dominating functionAPX-completenesweakly connected Roman domination

Mathematics Subject Classification ID

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

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Algorithmic aspects of \(b\)-disjunctive domination in graphs
• Approximation hardness of dominating set problems in bounded degree 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
• Improved integer linear programming formulation for weak Roman domination problem
• Algorithmic aspects of semitotal domination in graphs
• Defending the Roman Empire---a new strategy
• Threshold graphs and related topics
• Algorithmic aspects of Roman domination in graphs
• Weakly connected Roman domination in graphs
• The monadic second-order logic of graphs. I: Recognizable sets of finite graphs
• Defendens Imperium Romanum: A Classical Problem in Military Strategy
• Algorithm and Hardness Results for Outer-connected Dominating Set in Graphs
• Solving the Connected Dominating Set Problem and Power Dominating Set Problem by Integer Programming
• A characterization of Roman trees
• Integer linear programming formulations for double roman domination problem
• Improved mixed integer linear programing formulations for roman domination problem
• A new mixed integer linear programming formulation for the maximum degree bounded connected subgraph problem
• Node-and edge-deletion NP-complete problems
• Algorithms and Computation

This page was built for publication: Algorithmic complexity of weakly connected Roman domination in graphs