کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
6872240 | 681647 | 2014 | 9 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Solving Capacitated Dominating Set by using covering by subsets and maximum matching
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
چکیده انگلیسی
The Capacitated Dominating Set problem is the problem of finding a dominating set of minimum cardinality where each vertex has been assigned a bound on the number of vertices it has capacity to dominate. Cygan et al. showed in 2009 that this problem can be solved in O(n3mnn/3) or in Oâ(1.89n) time using maximum matching algorithm. An alternative way to solve this problem is to use dynamic programming over subsets. By exploiting structural properties of instances that cannot be solved fast by the maximum matching approach, and “hiding” additional cost related to considering subsets of large cardinality in the dynamic programming, an improved algorithm is obtained. We show that the Capacitated Dominating Set problem can be solved in Oâ(1.8463n) time.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Applied Mathematics - Volume 168, 11 May 2014, Pages 60-68
Journal: Discrete Applied Mathematics - Volume 168, 11 May 2014, Pages 60-68
نویسندگان
Mathieu Liedloff, Ioan Todinca, Yngve Villanger,