Algorithmic aspects of certified domination in graphs

DOI10.22049/CCO.2021.27302.1226MaRDI QIDQ6101494zbMATH OpenOpenAlexFDO

Authors

Publication date 1 June 2023

Full work available at URL http://comb-opt.azaruniv.ac.ir/article_14269_8f418c5112b2e5fec152287cbe0d932c.pdf

zbMATH Keywords

certified dominationNP-completenesstree-convex bipartite graphs

Mathematics Subject Classification ID

Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Analysis of algorithms and problem complexity (68Q25)

Recommendations

• Graphs with equal domination and certified domination numbers
• Dominating sets for split and bipartite graphs
• The complexity of secure domination problem in graphs
• Algorithmic complexity of secure connected domination in graphs

Cites work

• Algorithmic aspects of 2-secure domination in graphs
• Algorithmic aspects of total Roman \(\{3\}\)-domination in graphs
• Algorithmic complexity of secure connected domination in graphs
• Algorithms and Computation
• Certified domination
• scientific article; zbMATH DE number 1095171 (Why is no real title available?)
• scientific article; zbMATH DE number 1095172 (Why is no real title available?)
• On the double Roman domination in graphs
• Planar 3DM is NP-complete
• Reducibility among combinatorial problems
• The monadic second-order logic of graphs. I: Recognizable sets of finite graphs
• Threshold graphs and related topics
• Total \(k\)-rainbow domination numbers in graphs
• Two Hardness Results on Feedback Vertex Sets

Cited in

(8)

• On certificates and lookahead in dynamic graph problems
• Global triple Roman dominating function
• Certification of breadth-first algorithms by extraction
• Connected certified domination edge critical and stable graphs
• Certified hop domination in graphs
• A study on triple connected certified domination numbers in power graphs of triangular grids
• Certified domination critical graphs upon vertex removal
• Stability of certified domination upon edge addition

This page was built for publication: Algorithmic aspects of certified domination in graphs

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