کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
419736 | 683856 | 2009 | 10 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Approximation algorithms for the weighted independent set problem in sparse graphs
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله

چکیده انگلیسی
The approximability of the unweighted independent set problem has been analyzed in terms of sparseness parameters such as the average degree and inductiveness. In the weighted case, no corresponding results are possible for average degree, since adding vertices of small weight can decrease the average degree arbitrarily without significantly changing the approximation ratio. In this paper, we introduce two weighted measures, namely weighted average degree and weighted inductiveness, and analyze algorithms for the weighted independent set problem in terms of these parameters.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Applied Mathematics - Volume 157, Issue 4, 28 February 2009, Pages 617–626
Journal: Discrete Applied Mathematics - Volume 157, Issue 4, 28 February 2009, Pages 617–626
نویسندگان
Akihisa Kako, Takao Ono, Tomio Hirata, Magnús M. Halldórsson,