| Article ID | Journal | Published Year | Pages | File Type |
|---|---|---|---|---|
| 6871510 | Discrete Applied Mathematics | 2018 | 9 Pages |
Abstract
In this paper, we show that MWIS can be solved in polynomial time for (P7,triangle)-free graphs. This extends the corresponding result for (P6,triangle)-free graphs and may provide some progress in the study of MWIS for P7-free graphs such as the recent result by Maffray and Pastor (2016) showing that MWIS can be solved in polynomial time for (P7,bull)-free graphs.
Keywords
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Andreas Brandstädt, Raffaele Mosca,