The complexity of secure domination problem in graphs

DOI10.7151/dmgt.2008zbMath1390.05182OpenAlexW2738841429MaRDI QIDQ1708386

Hai-Chao Wang, Yun-Ping Deng, Yan-Cai Zhao

Publication date: 23 March 2018

Published in: Discussiones Mathematicae. Graph Theory (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.7151/dmgt.2008

zbMATH Keywords

NP-completenesssecure dominationdoubly chordal graphAPX-completenessstar convex bipartite graph

Mathematics Subject Classification ID

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

Related Items (14)

An improved binary programming formulation for the secure domination problem ⋮ Algorithmic results in secure total dominating sets on graphs ⋮ Secure domination of some graph operators ⋮ Complexity results on cosecure domination in graphs ⋮ Cosecure domination: hardness results and algorithms ⋮ Algorithmic aspects of secure domination in unit disk graphs ⋮ Some new algorithmic results on co-secure domination in graphs ⋮ On the complexity of co-secure dominating set problem ⋮ The secure domination problem in cographs ⋮ Correcting the algorithm for the secure domination number of cographs by Jha, Pradhan, and Banerjee ⋮ Secure total domination in chain graphs and cographs ⋮ Algorithmic aspects of secure connected domination in graphs ⋮ Eternal and Secure Domination in Graphs ⋮ The secure domination number of Cartesian products of small graphs with paths and cycles

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Dominating sets for split and bipartite graphs
• Irredundance, secure domination and maximum degree in trees
• Approximation hardness of dominating set problems in bounded degree graphs
• Hardness results and approximation algorithms of \(k\)-tuple domination in graphs
• Secure domination critical graphs
• Optimization, approximation, and complexity classes
• Some APX-completeness results for cubic graphs
• On secure domination in graphs
• Incidence matrices and interval graphs
• A linear algorithm for secure domination in trees
• Two Hardness Results on Feedback Vertex Sets
• Vertex Covers and Secure Domination in Graphs
• Secure domination and secure total domination in graphs
• Dually Chordal Graphs

This page was built for publication: The complexity of secure domination problem in graphs