Maximum independent sets in subclasses of P-5-free graphs
Lozin, Vadim V. and Mosca, Raffaele. (2009) Maximum independent sets in subclasses of P-5-free graphs. Information Processing Letters, Vol.109 (No.6). pp. 319-324. ISSN 0020-0190Full text not available from this repository.
Official URL: http://dx.doi.org/10.1016/j.ipl.2008.11.005
The class Of P-5-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 P-5-free graphs generalizing several previously known results. (C) 2008 Elsevier B.V. All rights reserved.
|Item Type:||Journal Article|
|Subjects:||Q Science > QA Mathematics > QA76 Electronic computers. Computer science. Computer software|
|Divisions:||Faculty of Science > Mathematics|
|Journal or Publication Title:||Information Processing Letters|
|Publisher:||Elsevier Science BV|
|Official Date:||28 February 2009|
|Number of Pages:||6|
|Page Range:||pp. 319-324|
|Access rights to Published version:||Restricted or Subscription Access|
Actions (login required)
Downloads per month over past year