Article ID Journal Published Year Pages File Type
418470 Discrete Applied Mathematics 2016 10 Pages PDF
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
, ,