کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
4949495 | 1440192 | 2017 | 11 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Linear kernels for k-tuple and liar's domination in bounded genus graphs
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
چکیده انگلیسی
A set DâV is called a k-tuple dominating set of a graph G=(V,E) if |NG[v]â©D|â¥k for all vâV, where NG[v] denotes the closed neighborhood of v. A set DâV is called a liar's dominating set of a graph G=(V,E) if (i) |NG[v]â©D|â¥2 for all vâV and (ii) for every pair of distinct vertices u,vâV, |(NG[u]âªNG[v])â©D|â¥3. Given a graph G, the decision versions of k-Tuple Domination Problem and the Liar's Domination Problem are to check whether there exist a k-tuple dominating set and a liar's dominating set of G of a given cardinality, respectively. These two problems are known to be NP-complete (Liao and Chang, 2003; Slater, 2009). In this paper, we study the parameterized complexity of these problems. We show that the k-Tuple Domination Problem and the Liar's Domination Problem are W[2]-hard for general graphs. It can be verified that both the problems have a finite integer index and satisfy certain coverability property. Hence they admit linear kernel as per the meta-theorem in Bodlaender (2009), but the meta-theorem says nothing about the constant. In this paper, we present a direct proof of the existence of linear kernel with small constants for both the problems.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Applied Mathematics - Volume 231, 20 November 2017, Pages 67-77
Journal: Discrete Applied Mathematics - Volume 231, 20 November 2017, Pages 67-77
نویسندگان
Arijit Bishnu, Arijit Ghosh, Subhabrata Paul,