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