کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
4949897 1364262 2017 7 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Maximum weight independent sets in classes related to claw-free graphs
ترجمه فارسی عنوان
مجموعه های حداکثر وزن مستقل در کلاس های مربوط به گراف های ناقص
کلمات کلیدی
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر نظریه محاسباتی و ریاضیات
چکیده انگلیسی

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