کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
4949897 | 1364262 | 2017 | 7 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Maximum weight independent sets in classes related to claw-free graphs
ترجمه فارسی عنوان
مجموعه های حداکثر وزن مستقل در کلاس های مربوط به گراف های ناقص
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
مجموعه مستقل، بدون پره
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
چکیده انگلیسی
The Maximum Weight Independent Set (MWIS) problem on graphs with vertex weights asks for a set of pairwise nonadjacent vertices of maximum total weight. The complexity of the MWIS problem for S1,1,3-free graphs, and for S1,2,2-free graphs is unknown. We show that the MWIS problem in (S1,1,3, banner)-free graphs, and in (S1,2,2, bull)-free graphs can be solved in polynomial time. These results extend some known results in the literature.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Applied Mathematics - Volume 216, Part 1, 10 January 2017, Pages 233-239
Journal: Discrete Applied Mathematics - Volume 216, Part 1, 10 January 2017, Pages 233-239
نویسندگان
T. Karthick, Frédéric Maffray,