کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
6871510 1440187 2018 9 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Maximum Weight Independent Sets for (P7,triangle)-free graphs in polynomial time
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
Maximum Weight Independent Sets for (P7,triangle)-free graphs in polynomial time
چکیده انگلیسی
In this paper, we show that MWIS can be solved in polynomial time for (P7,triangle)-free graphs. This extends the corresponding result for (P6,triangle)-free graphs and may provide some progress in the study of MWIS for P7-free graphs such as the recent result by Maffray and Pastor (2016) showing that MWIS can be solved in polynomial time for (P7,bull)-free graphs.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Applied Mathematics - Volume 236, 19 February 2018, Pages 57-65
نویسندگان
, ,