Addendum to: Maximum Weight Independent Sets in hole- and co-chair-free graphs
The Maximum Weight Independent Set (MWIS) problem on graphs is a frequently studied problem. Clique separators and modular decomposition are powerful tools for solving this problem on various graph classes. We combine these tools for solving MWIS efficiently on odd-hole- and co-chair-free graphs by showing that atoms of prime odd-hole- and co-chair-free graphs are nearly perfect and atoms of prime hole- and co-chair-free graphs are nearly weakly chordal.
modular decomposition graph algorithms maximum weight independent set problem clique separator decomposition odd-hole-free graphs perfect graphs