کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
8903030 | 1632399 | 2018 | 10 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Maximum weight stable set in (P7, bull)-free graphs and (S1,2,3, bull)-free graphs
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
موضوعات مرتبط
مهندسی و علوم پایه
ریاضیات
ریاضیات گسسته و ترکیبات
پیش نمایش صفحه اول مقاله

چکیده انگلیسی
We give a polynomial time algorithm that finds the maximum weight stable set in a graph that does not contain an induced path on seven vertices or a bull (the graph with vertices a,b,c,d,e and edges ab,bc,cd,be,ce). With the same arguments we also give a polynomial algorithm for any graph that does not contain S1,2,3 or a bull.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Mathematics - Volume 341, Issue 5, May 2018, Pages 1449-1458
Journal: Discrete Mathematics - Volume 341, Issue 5, May 2018, Pages 1449-1458
نویسندگان
Frédéric Maffray, Lucas Pastor,