کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
6871463 1440186 2018 8 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Maximum weight independent set for ℓclaw-free graphs in polynomial time
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
Maximum weight independent set for ℓclaw-free graphs in polynomial time
چکیده انگلیسی
In this paper, using a dynamic programming approach (inspired by Farber's result about MWIS for 2K2-free graphs), we show that for any fixed ℓ, MWIS can be solved in polynomial time for ℓclaw-free graphs. This solves the open cases for MWIS on (P3+ claw)-free graphs and on (2K2+claw)-free graphs and extends known results for claw-free graphs, ℓK2-free graphs, (K2+claw)-free graphs, and ℓP3-free graphs.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Applied Mathematics - Volume 237, 11 March 2018, Pages 57-64
نویسندگان
, ,