Article ID Journal Published Year Pages File Type
6871463 Discrete Applied Mathematics 2018 8 Pages PDF
Abstract
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.
Keywords
Related Topics
Physical Sciences and Engineering Computer Science Computational Theory and Mathematics
Preview
Maximum weight independent set for ℓclaw-free graphs in polynomial time
Authors
, ,