On computing a minimum secure dominating set in block graphs

DOI10.1007/s10878-017-0197-yzbMath1386.05143OpenAlexW2767964623MaRDI QIDQ1702842

Anupriya Jha, Dina Pradhan

Publication date: 1 March 2018

Published in: Journal of Combinatorial Optimization (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s10878-017-0197-y

zbMATH Keywords

NP-completenesslinear time algorithmdominationblock graphssecure domination

Mathematics Subject Classification ID

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

Related Items

An improved binary programming formulation for the secure domination problem ⋮ A linear-time algorithm for weighted paired-domination on block graphs ⋮ A heuristic approximation algorithm of minimum dominating set based on rough set theory ⋮ Secure domination in cographs ⋮ Secure domination of some graph operators ⋮ Algorithmic aspects of secure domination in unit disk graphs ⋮ The secure domination problem in cographs ⋮ Correcting the algorithm for the secure domination number of cographs by Jha, Pradhan, and Banerjee ⋮ Secure domination in rooted product graphs ⋮ Secure total domination in chain graphs and cographs ⋮ Eternal and Secure Domination in Graphs ⋮ The secure domination number of Cartesian products of small graphs with paths and cycles ⋮ Roman \(\{2\}\)-domination problem in graphs

Cites Work

• Irredundance, secure domination and maximum degree in trees
• Optimal vertex ranking of block graphs
• Labelling algorithms for paired-domination problems in block and interval graphs
• Secure domination critical graphs
• The NP-completeness of Steiner tree and dominating set for chordal bipartite graphs
• On secure domination in graphs
• A linear algorithm for secure domination in trees
• Node-searching problem on block graphs
• Power domination in block graphs
• Vertex Covers and Secure Domination in Graphs
• Secure domination and secure total domination in graphs
• Graph Classes: A Survey
• On minimum secure dominating sets of graphs
• \(k\)-power domination in block graphs
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item