On computing a minimum secure dominating set in block graphs

DOI10.1007/S10878-017-0197-YMaRDI QIDQ1702842zbMATH OpenOpenAlexFDO

Authors 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-completenessdominationlinear time algorithmblock graphssecure domination

Mathematics Subject Classification ID

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

Recommendations

• On secure domination in graphs
• The complexity of secure domination problem in graphs
• The secure domination problem in cographs
• Algorithmic complexity of secure connected domination in graphs
• On computing secure domination of trees

Cites work

• scientific article; zbMATH DE number 3511563 (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?)
• scientific article; zbMATH DE number 2114685 (Why is no real title available?)
• scientific article; zbMATH DE number 2188604 (Why is no real title available?)
• A linear algorithm for secure domination in trees
• Edge stability in secure graph domination
• Graph Classes: A Survey
• Irredundance, secure domination and maximum degree in trees
• Labelling algorithms for paired-domination problems in block and interval graphs
• Node-searching problem on block graphs
• On minimum secure dominating sets of graphs
• On secure domination in graphs
• Optimal vertex ranking of block graphs
• Power domination in block graphs
• Secure domination and secure total domination in graphs
• Secure domination critical graphs
• The NP-completeness of Steiner tree and dominating set for chordal bipartite graphs
• Two algorithms for secure graph domination
• Vertex Covers and Secure Domination in Graphs
• \(k\)-power domination in block graphs

Cited in

(22)

• Secure domination in cographs
• An improved binary programming formulation for the secure domination problem
• Secure domination of some graph operators
• Correcting the algorithm for the secure domination number of cographs by Jha, Pradhan, and Banerjee
• Algorithmic aspects of secure connected domination in graphs
• The complexity of secure domination problem in graphs
• On maximal Roman domination in graphs: complexity and algorithms
• Secure domination in rooted product graphs
• Eternal and Secure Domination in Graphs
• A linear-time algorithm for weighted paired-domination on block graphs
• A lower bound for secure domination number of an outerplanar graph
• PTASs for secure dominating set in planar graphs and growth-bounded graphs
• Secure total domination in chain graphs and cographs
• Algorithmic aspects of secure domination in unit disk graphs
• On secure domination in graphs
• A heuristic approximation algorithm of minimum dominating set based on rough set theory
• The secure domination number of Cartesian products of small graphs with paths and cycles
• Roman \(\{2\}\)-domination problem in graphs
• Algorithmic complexity of secure connected domination in graphs
• The secure domination problem in cographs
• The strong domination problem in block graphs and proper interval graphs
• Secure total domination number in maximal outerplanar graphs

This page was built for publication: On computing a minimum secure dominating set in block graphs

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