Journal of Graph Algorithms and Applications
http://jgaa.info ISSN: 1526-1719
|
DOI: 10.7155/jgaa.00207 On the Maximum Independent Set Problem in Subclasses of Planar Graphs Vadim Lozin and Martin Milanič Vol. 14, no. 2, pp. 269-286, 2010. Regular paper Abstract The maximum independent set problem is known to be NP-hard in the class of planar graphs. In the present paper, we study its complexity in hereditary subclasses of planar graphs. In particular, by combining various techniques, we show that the problem is polynomially solvable in the class of S1,2,k-free planar graphs, generalizing several previously known results. S1,2,k is the graph consisting of three induced paths of lengths 1, 2 and k, with a common initial vertex.
|
Published: June 2010. Final: March 2010. Submitted: July 2007. Revised: June 2009. Reviewed: May 2009. Accepted: March 2010. Communicated by Martin Fürer |
| Journal of Graph Algorithms and Applications |