کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
428317 | 686633 | 2006 | 4 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
On the multi-radius cover problem
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله

چکیده انگلیسی
An instance of the multi-radius cover problem consists of a graph G=(V,E) with edge lengths . Each vertex u∈V represents a transmission station for which a transmission radius ru must be picked. Edges represent a continuum of demand points to be satisfied, that is, for every edge (u,v)∈E we ask that ru+rv⩾luv. The cost of transmitting at radius r from vertex u is given by an arbitrary non-decreasing cost function cu(r). Our goal is to find a cover with minimum total cost ∑ucu(ru).The multi-radius cover problem is NP-hard as it generalizes the well-known vertex cover problem. In this paper we present a 2-approximation algorithm for it.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Information Processing Letters - Volume 99, Issue 5, 15 September 2006, Pages 195-198
Journal: Information Processing Letters - Volume 99, Issue 5, 15 September 2006, Pages 195-198