Algorithmic aspects of secure domination in unit disk graphs

DOI10.1016/J.IC.2023.105090MaRDI QIDQ6186318zbMATH OpenOpenAlexFDO

Authors Cai-Xia Wang, Yu Yang, S. J. Xu

Publication date 2 February 2024

Published in Information and Computation (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.ic.2023.105090

zbMATH Keywords

approximation algorithmNP-completesecure dominationunit disk graph

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Cites work

• A better heuristic for orthogonal graph drawings
• A linear algorithm for secure domination in trees
• A polynomial-time approximation scheme for the minimum-connected dominating set in ad hoc wireless networks
• APPROXIMATION ALGORITHMS FOR A VARIANT OF DISCRETE PIERCING SET PROBLEM FOR UNIT DISKS
• Approximation and Online Algorithms
• Efficient sub-5 approximations for minimum dominating sets in unit disk graphs
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 2188604 (Why is no real title available?)
• Liar's dominating set problem on unit disk graphs
• Liar's domination in unit disk graphs
• On computing a minimum secure dominating set in block graphs
• On secure domination in graphs
• Secure connected domination and secure total domination in unit disk graphs and rectangle graphs
• Simple heuristics for unit disk graphs
• The complexity of secure domination problem in graphs
• Tighter approximation bounds for minimum CDS in wireless ad hoc networks
• Two algorithms for secure graph domination
• Unit disk graphs
• Universality considerations in VLSI circuits

Cited in

(3)

• A survey on variant domination problems in geometric intersection graphs
• The algorithm and complexity of co-secure domination in geometric intersection graphs
• The algorithm and complexity of secure domination in 3-dimensional box graphs

This page was built for publication: Algorithmic aspects of secure domination in unit disk graphs

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