Algorithmic complexity of weakly connected Roman domination in graphs

DOI10.1142/S1793830921501251MaRDI QIDQ5866025zbMATH OpenOpenAlexFDO

Authors Padamutham Chakradhar, Palagiri Venkata Subba Reddy, Khandelwal Himanshu

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

\(NP\)-completenessAPX-completenesinteger linear programmingRoman dominating functionweakly connected Roman domination

Mathematics Subject Classification ID

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

Recommendations

• Algorithmic aspects of Roman domination in graphs
• Algorithmic and complexity aspects of problems related to total Roman domination for graphs
• Algorithmic Aspects of Quasi-Total Roman Domination in Graphs
• Weakly connected Roman domination in graphs
• Algorithmic results in Roman dominating functions on graphs
• scientific article; zbMATH DE number 7693181
• Complexity aspects of restrained Roman domination in graphs
• Weak Roman domination in graphs
• scientific article; zbMATH DE number 6129508
• Efficient algorithms for Roman domination on some classes of graphs

Cites work

• A characterization of Roman trees
• A new mixed integer linear programming formulation for the maximum degree bounded connected subgraph problem
• Algorithm and Hardness Results for Outer-connected Dominating Set in Graphs
• Algorithmic aspects of \(b\)-disjunctive domination in graphs
• Algorithmic aspects of Roman domination in graphs
• Algorithmic aspects of semitotal domination in graphs
• Algorithms and Computation
• Approximation hardness of dominating set problems in bounded degree graphs
• Defendens Imperium Romanum: A Classical Problem in Military Strategy
• Defending the Roman Empire from multiple attacks
• Defending the Roman Empire---a new strategy
• Efficient algorithms for Roman domination on some classes of graphs
• scientific article; zbMATH DE number 5764849 (Why is no real title available?)
• 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?)
• Improved integer linear programming formulation for weak Roman domination problem
• Improved mixed integer linear programing formulations for Roman domination problem
• Integer linear programming formulations for double Roman domination problem
• Node-and edge-deletion NP-complete problems
• On the Roman domination number of a graph
• Optimization, approximation, and complexity classes
• Roman domination in graphs.
• Roman domination perfect graphs
• Solving the connected dominating set problem and power dominating set problem by integer programming
• 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
• Weakly connected Roman domination in graphs

Cited in

(4)

• Nearly tight approximation algorithm for (connected) Roman dominating set
• Exact algorithms for weak Roman domination
• Exact Algorithms for Weak Roman Domination
• Algorithmic results for weak Roman domination problem in graphs

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

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