کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
10333176 | 688607 | 2009 | 9 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Greedy approximation for the source location problem with vertex-connectivity requirements in undirected graphs
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
چکیده انگلیسی
In this paper, we consider the problem in the case where every vertex has uniform cost. We propose a simple greedy algorithm for providing a max{dâ,2dââ6}-approximate solution to the problem in O(min{dâ,|V|}dâ|V|2) time, while we also show that there exists an instance for which it provides no better than a (dââ1)-approximate solution. Especially, in the case of dâ⩽4, we give a tight analysis to show that it achieves an approximation ratio of 3. We also show the APX-hardness of the problem even restricted to dâ⩽4.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Journal of Discrete Algorithms - Volume 7, Issue 4, December 2009, Pages 570-578
Journal: Journal of Discrete Algorithms - Volume 7, Issue 4, December 2009, Pages 570-578
نویسندگان
Toshimasa Ishii,