کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
6871463 | 1440186 | 2018 | 8 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Maximum weight independent set for âclaw-free graphs in polynomial time
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
![عکس صفحه اول مقاله: Maximum weight independent set for âclaw-free graphs in polynomial time Maximum weight independent set for âclaw-free graphs in polynomial time](/preview/png/6871463.png)
چکیده انگلیسی
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
Journal: Discrete Applied Mathematics - Volume 237, 11 March 2018, Pages 57-64
نویسندگان
Andreas Brandstädt, Raffaele Mosca,