Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
418470 | Discrete Applied Mathematics | 2016 | 10 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 P6P6-free graphs, and for S1,2,2S1,2,2-free graphs are unknown. In this note, we give a proof for the solvability of the MWIS problem for (P6P6, S1,2,2S1,2,2, co-chair)-free graphs in polynomial time, by analyzing the structure and the MWIS problem in various subclasses of (P6P6, S1,2,2S1,2,2, co-chair)-free graphs. These results extend some known results in the literature.
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
T. Karthick, Frédéric Maffray,