کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
436200 | 689977 | 2009 | 10 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
A 5+ϵ-approximation algorithm for minimum weighted dominating set in unit disk graph
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
چکیده انگلیسی
We study the minimum weight dominating set problem in weighted unit disk graph, and give a polynomial time algorithm with approximation ratio 5+ϵ, improving the previous best result of 6+ϵ in [Yaochun Huang, Xiaofeng Gao, Zhao Zhang, Weili Wu, A better constant-factor approximation for weighted dominating set in unit disk graph, J. Comb. Optim. (ISSN: 1382-6905) (2008) 1573–2886. (Print) (Online)]. Combining the common technique used in the above mentioned reference, we can compute a minimum weight connected dominating set with approximation ratio 9+ϵ, beating the previous best result of 10+ϵ in the same work.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Theoretical Computer Science - Volume 410, Issues 8–10, 1 March 2009, Pages 756-765
Journal: Theoretical Computer Science - Volume 410, Issues 8–10, 1 March 2009, Pages 756-765