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

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
نویسندگان
, , , ,