کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
6871721 | 1440189 | 2018 | 21 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
The probabilistic minimum dominating set problem
ترجمه فارسی عنوان
حداقل احتمال احتمالی مشکل مجموعه
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
پیچیدگی، نزدیک شدن بهینه سازی احتمالی، غرور مجموعه، شبکه های حسگر بی سیم،
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
چکیده انگلیسی
We present a natural wireless sensor network problem, which we model as a probabilistic version of the min dominating set problem (called probabilistic min dominating set). We first show that calculation of the objective function of this general probabilistic problem is #P-complete. We then introduce a restricted version of probabilistic min dominating set and show that, this time, calculation of its objective function can be performed in polynomial time and that this restricted problem is “just” NP-hard, since it is a generalization of the classical min dominating set. We study the complexity of this restricted version in graphs where min dominating set is polynomial, mainly in trees and paths and then we give some approximation results for it.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Applied Mathematics - Volume 234, 10 January 2018, Pages 93-113
Journal: Discrete Applied Mathematics - Volume 234, 10 January 2018, Pages 93-113
نویسندگان
Nicolas Boria, Cécile Murat, Vangelis Th. Paschos,