Title of article
Polar graphs and maximal independent sets Original Research Article
Author/Authors
Vadim V. Lozin، نويسنده , , Raffaele Mosca، نويسنده ,
Issue Information
روزنامه با شماره پیاپی سال 2006
Pages
8
From page
2901
To page
2908
Abstract
We study two central problems of algorithmic graph theory: finding maximum and minimum maximal independent sets. Both problems are known to be NP-hard in general. Moreover, they remain NP-hard in many special classes of graphs. For instance, the problem of finding minimum maximal independent sets has been recently proven to be NP-hard in the class of so-called
Keywords
Maximal independent set , Polynomial-time algorithm
Journal title
Discrete Mathematics
Serial Year
2006
Journal title
Discrete Mathematics
Record number
947906
Link To Document