کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
6897403 | 1446028 | 2014 | 9 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
On connected dominating sets of restricted diameter
ترجمه فارسی عنوان
در مجموعه متمرکز متصل شده از قطر محدود
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
علوم کامپیوتر (عمومی)
چکیده انگلیسی
A connected dominating set (CDS) is commonly used to model a virtual backbone of a wireless network. To bound the distance that information must travel through the network, we explicitly restrict the diameter of a CDS to be no more than s leading to the concept of a dominating s-club. We prove that for any fixed positive integer s it is NP-complete to determine if a graph has a dominating s-club, even when the graph has diameter s+1. As a special case it is NP-complete to determine if a graph of diameter two has a dominating clique. We then propose a compact integer programming formulation for the related minimization problem, enhance the approach with variable fixing rules and valid inequalities, and present computational results.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: European Journal of Operational Research - Volume 236, Issue 2, 16 July 2014, Pages 410-418
Journal: European Journal of Operational Research - Volume 236, Issue 2, 16 July 2014, Pages 410-418
نویسندگان
Austin Buchanan, Je Sang Sung, Vladimir Boginski, Sergiy Butenko,