Algorithmic results for weak Roman domination problem in graphs

DOI10.1016/J.DAM.2024.08.007MaRDI QIDQ6633543zbMATH OpenFDO

Authors Kaustav K. Paul, Ankit Sharma, Arti Pandey

Publication date 6 November 2024

Published in Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/J.DAM.2024.08.007

zbMATH Keywords

graph algorithmsNP-completenessbipartite graphssplit graphs\(P_4\)-sparse graphsweak Roman dominating function

Mathematics Subject Classification ID

Algorithms in computer science (68Wxx) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Theory of computing (68Qxx)

Recommendations

• Algorithmic aspects of Roman domination in graphs
• Algorithmic complexity of weakly connected Roman domination in graphs
• Algorithmic results on double Roman domination in graphs
• Some results of weak Roman domination number in graphs

Cites work

• A characterization of Roman trees
• Clustering to minimize the maximum intercluster distance
• Defending the Roman Empire---a new strategy
• Domination in some subclasses of bipartite graphs
• Exact algorithms for weak Roman domination
• Introduction to algorithms.
• On some domination colorings of graphs
• Roman domination in graphs.
• Some APX-completeness results for cubic graphs

Cited in

(3)

• Exploring algorithmic solutions for the independent Roman domination problem in graphs
• Finding maximum edge bicliques in tree convex graphs
• Decomposing convex bipartite graphs into biconvex graphs and enumerating minimum weight red blue dominating sets

This page was built for publication: Algorithmic results for weak Roman domination problem in graphs

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