کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
421161 | 684151 | 2014 | 11 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
On the algorithmic complexity of kk-tuple total domination
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
چکیده انگلیسی
For a fixed positive integer kk, a kk-tuple total dominating set of a graph GG is a set D⊆V(G)D⊆V(G) such that every vertex of GG is adjacent to at least kk vertices in DD. The kk-tuple total domination problem is to determine a minimum kk-tuple total dominating set of GG. This paper studies kk-tuple total domination from an algorithmic point of view. In particular, we present a linear-time algorithm for the kk-tuple total domination problem for graphs in which each block is a clique, a cycle or a complete bipartite graph, which include trees, block graphs, cacti and block-cactus graphs. We also establish NP-hardness of the kk-tuple total domination problem in undirected path graphs.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Applied Mathematics - Volume 174, 10 September 2014, Pages 81–91
Journal: Discrete Applied Mathematics - Volume 174, 10 September 2014, Pages 81–91
نویسندگان
James K. Lan, Gerard Jennhwa Chang,