The Library
The maximum independent set problem in planar graphs
Tools
Alekseev, Vladimir E., Lozin, Vadim V., Malyshev, Dmitriy and Milanič, Martin (2008) The maximum independent set problem in planar graphs. Lecture Notes in Computer Science, Vol.5162 . pp. 96-107. doi:10.1007/978-3-540-85238-4_7 ISSN 0302-9743.
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://dx.doi.org/10.1007/978-3-540-85238-4_7
Abstract
We study the computational complexity of finding a maximum independent set of vertices in a planar graph. In general, this problem is known to be NP-hard. However, under certain restrictions it becomes polynomial-time solvable. We identify a graph parameter to which the complexity of the problem is sensible and produce a number of both negative (intractable) and positive (solvable in polynomial time) results, generalizing several known facts.
Item Type: | Journal Article | ||||
---|---|---|---|---|---|
Subjects: | Q Science > QA Mathematics | ||||
Divisions: | Faculty of Science, Engineering and Medicine > Science > Mathematics | ||||
Journal or Publication Title: | Lecture Notes in Computer Science | ||||
Publisher: | Springer | ||||
ISSN: | 0302-9743 | ||||
Book Title: | Mathematical Foundations of Computer Science 2008 | ||||
Official Date: | 2008 | ||||
Dates: |
|
||||
Volume: | Vol.5162 | ||||
Page Range: | pp. 96-107 | ||||
DOI: | 10.1007/978-3-540-85238-4_7 | ||||
Status: | Peer Reviewed | ||||
Publication Status: | Published | ||||
Access rights to Published version: | Restricted or Subscription Access | ||||
Description: | MATHEMATICAL FOUNDATIONS OF COMPUTER SCIENCE 2008 |
Request changes or add full text files to a record
Repository staff actions (login required)
View Item |