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