کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
8900740 | 1631719 | 2018 | 9 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Algorithm and complexity of the two disjoint connected dominating sets problem on trees
ترجمه فارسی عنوان
الگوریتم و پیچیدگی دو مسئله مجموعه غالب متصل به یکپارچه در درختان
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
موضوعات مرتبط
مهندسی و علوم پایه
ریاضیات
ریاضیات کاربردی
چکیده انگلیسی
In this paper, we consider a variation of the classic dominating set problem - The Two Disjoint Connected Dominating Sets (DCDS) problem, which finds applications in many real domains including wireless sensor networks. In the DCDS problem, we are given a graph G=(V,E) and required to find a new edge set Eâ² with minimum cardinality such that the resulting new graph after the adding of Eâ² has a pair of disjoint connected dominating sets. This problem is very hard in general graphs, and we show that it is NP-hard even restricted to trees. We also present a polynomial time approximation algorithm for the DCDS problem for arbitrary trees with performance ratio 32 asymptotically.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Applied Mathematics and Computation - Volume 337, 15 November 2018, Pages 419-427
Journal: Applied Mathematics and Computation - Volume 337, 15 November 2018, Pages 419-427
نویسندگان
Xianliang Liu, Zishen Yang, Wei Wang,