Algorithmic aspects of secure domination in unit disk graphs

DOI10.1016/j.ic.2023.105090OpenAlexW4386511355MaRDI QIDQ6186318

Cai-Xia Wang, Yu Yang, Shou-Jun 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

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unit disk graphs
• A better heuristic for orthogonal graph drawings
• On computing a minimum secure dominating set in block graphs
• The complexity of secure domination problem in graphs
• Liar's dominating set problem on unit disk graphs
• Liar's domination in unit disk graphs
• On secure domination in graphs
• A linear algorithm for secure domination in trees
• Efficient sub-5 approximations for minimum dominating sets in unit disk graphs
• Secure connected domination and secure total domination in unit disk graphs and rectangle graphs
• APPROXIMATION ALGORITHMS FOR A VARIANT OF DISCRETE PIERCING SET PROBLEM FOR UNIT DISKS
• Tighter Approximation Bounds for Minimum CDS in Wireless Ad Hoc Networks
• Universality considerations in VLSI circuits
• A polynomial-time approximation scheme for the minimum-connected dominating set in ad hoc wireless networks
• Simple heuristics for unit disk graphs
• Approximation and Online Algorithms

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