• A
  • A
  • A
  • ABC
  • ABC
  • ABC
  • А
  • А
  • А
  • А
  • А
Regular version of the site

Article

The Maximum Independent Set Problem in Planar Graphs

Lecture Notes in Computer Science. 2008. Vol. 5162. No. 4. P. 96-107.
Alekseev V., Lozin V. V., Malyshev D., Milanic M.

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.