Algorithmic aspects of secure domination in unit disk graphs

被引：3
作者：
Wang, Cai-Xia [1 ]
Yang, Yu [1 ]
Xu, Shou-Jun [1 ]
机构：
[1] Lanzhou Univ, Gansu Ctr Appl Math, Sch Math & Stat, Lanzhou 730000, Gansu, Peoples R China
来源：
INFORMATION AND COMPUTATION | 2023年 / 295卷
基金：
中国国家自然科学基金;
关键词：
Secure domination; Unit disk graph; NP-complete; Approximation algorithm; SET PROBLEM;
D O I：
10.1016/j.ic.2023.105090
中图分类号：
TP301 [理论、方法];
学科分类号：
081202 ;
摘要：
Given a graph G with vertex set V, a set S subset of V is a secure dominating set of G if S is a dominating set of G and if for every vertex u is an element of V \ S, there exists a vertex v is an element of S adjacent to u such that (S boolean OR {u}) \ {v} is a dominating set of G.The minimum secure dominating set (or, for short, MSDS) problem asks to find an MSDS in a given graph. In this paper, we first show that the decision version of the MSDS problem is NP-complete in unit disk graphs, even in grid graphs. Secondly, we give an O(n + m) time t-approximation algorithm for the MSDS problem in several geometric intersection graphs which are K1,t-free for some integer t >= 3. Finally, we propose a PTAS for the MSDS problem in unit disk graphs.(c) 2023 Elsevier Inc. All rights reserved.
引用
收藏
页数：11
相关论文
共 24 条
[1]   A better heuristic for orthogonal graph drawings [J].
Biedl, T ;
Kant, G .
COMPUTATIONAL GEOMETRY-THEORY AND APPLICATIONS, 1998, 9 (03) :159-180
[2]   A linear algorithm for secure domination in trees [J].
Burger, A. P. ;
de Villiers, A. P. ;
van Vuuren, J. H. .
DISCRETE APPLIED MATHEMATICS, 2014, 171 :15-27
[3]  
Burger A.P., 2013, J. Combin. Math. Combin. Comput., V85, P321
[4]  
Cadei M., 2002, 6 JCIS
[5]   A polynomial-time approximation scheme for the minimum-connected dominating set in ad hoc wireless networks [J].
Cheng, XZ ;
Huang, X ;
Li, DY ;
Wu, WL ;
Du, DZ .
NETWORKS, 2003, 42 (04) :202-208
[6]   UNIT DISK GRAPHS [J].
CLARK, BN ;
COLBOURN, CJ ;
JOHNSON, DS .
DISCRETE MATHEMATICS, 1990, 86 (1-3) :165-177
[7]  
Cockayne EJ, 2005, UTILITAS MATHEMATICA, V67, P19
[8]   Efficient sub-5 approximations for minimum dominating sets in unit disk graphs [J].
da Fonseca, Guilherme D. ;
de Figueiredo, Celina M. H. ;
Pereira de Sa, Vinicius G. ;
Machado, Raphael C. S. .
THEORETICAL COMPUTER SCIENCE, 2014, 540 :70-81
[9]   APPROXIMATION ALGORITHMS FOR A VARIANT OF DISCRETE PIERCING SET PROBLEM FOR UNIT DISKS [J].
De, Minati ;
Das, Gautam K. ;
Carmi, Paz ;
Nandy, Subhas C. .
INTERNATIONAL JOURNAL OF COMPUTATIONAL GEOMETRY & APPLICATIONS, 2013, 23 (06) :461-477
[10]  
Garey M. R., 1979, Computers and intractability. A guide to the theory of NP-completeness
123