| Article ID | Journal | Published Year | Pages | File Type |
|---|---|---|---|---|
| 4949897 | Discrete Applied Mathematics | 2017 | 7 Pages |
Abstract
The Maximum Weight Independent Set (MWIS) problem on graphs with vertex weights asks for a set of pairwise nonadjacent vertices of maximum total weight. The complexity of the MWIS problem for S1,1,3-free graphs, and for S1,2,2-free graphs is unknown. We show that the MWIS problem in (S1,1,3, banner)-free graphs, and in (S1,2,2, bull)-free graphs can be solved in polynomial time. These results extend some known results in the literature.
Keywords
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
T. Karthick, Frédéric Maffray,