| Article ID | Journal | Published Year | Pages | File Type |
|---|---|---|---|---|
| 427862 | Information Processing Letters | 2009 | 6 Pages |
Abstract
The class of P5-free graphs is the unique minimal class defined by a single connected forbidden induced subgraph for which the complexity status of the maximum independent set problem is unknown. In this paper, we prove polynomial-time solvability of the problem in two subclasses of P5-free graphs generalizing several previously known results.
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
