کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
6871510 | 1440187 | 2018 | 9 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Maximum Weight Independent Sets for (P7,triangle)-free graphs in polynomial time
دانلود مقاله + سفارش ترجمه
دانلود مقاله 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](/preview/png/6871510.png)
چکیده انگلیسی
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
Journal: Discrete Applied Mathematics - Volume 236, 19 February 2018, Pages 57-65
نویسندگان
Andreas Brandstädt, Raffaele Mosca,