The Library
On the maximum independent set problem in subclasses of planar graphs
Tools
Lozin, Vadim V. and Milanic, Martin (2010) On the maximum independent set problem in subclasses of planar graphs. Journal of Graph Algorithms and Applications, Vol.14 (No.2). pp. 269-286. ISSN 1526-1719.
Research output not available from this repository.
Request-a-Copy directly from author or use local Library Get it For Me service.
Official URL: http://www.jgaa.info
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.
Item Type: | Journal Article | ||||
---|---|---|---|---|---|
Subjects: | Q Science > QA Mathematics | ||||
Divisions: | Faculty of Science, Engineering and Medicine > Science > Mathematics | ||||
Journal or Publication Title: | Journal of Graph Algorithms and Applications | ||||
Publisher: | Brown University, Department of Computer Science | ||||
ISSN: | 1526-1719 | ||||
Official Date: | June 2010 | ||||
Dates: |
|
||||
Volume: | Vol.14 | ||||
Number: | No.2 | ||||
Page Range: | pp. 269-286 | ||||
Status: | Peer Reviewed | ||||
Publication Status: | Published | ||||
Access rights to Published version: | Restricted or Subscription Access |
Request changes or add full text files to a record
Repository staff actions (login required)
View Item |