Geodesic
On the Maximum Independent Set Problem in Subclasses of Planar Graphs
Journal of Graph Algorithms and Applications, Tome 14 (2010) no. 2, pp. 269-286.

Voir la notice de l'article provenant de la source Journal of Graph Algorythms and Applications website

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. 
@article{JGAA_2010_14_2_a6,
     author = {Vadim Lozin and Martin Milani\v{c}},
     title = {On the {Maximum} {Independent} {Set} {Problem} in {Subclasses} of {Planar} {Graphs}},
     journal = {Journal of Graph Algorithms and Applications},
     pages = {269--286},
     publisher = {mathdoc},
     volume = {14},
     number = {2},
     year = {2010},
     doi = {10.7155/jgaa.00207},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00207/}
}
TY  - JOUR
AU  - Vadim Lozin
AU  - Martin Milanič
TI  - On the Maximum Independent Set Problem in Subclasses of Planar Graphs
JO  - Journal of Graph Algorithms and Applications
PY  - 2010
SP  - 269
EP  - 286
VL  - 14
IS  - 2
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00207/
DO  - 10.7155/jgaa.00207
LA  - en
ID  - JGAA_2010_14_2_a6
ER  - 
%0 Journal Article
%A Vadim Lozin
%A Martin Milanič
%T On the Maximum Independent Set Problem in Subclasses of Planar Graphs
%J Journal of Graph Algorithms and Applications
%D 2010
%P 269-286
%V 14
%N 2
%I mathdoc
%U http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00207/
%R 10.7155/jgaa.00207
%G en
%F JGAA_2010_14_2_a6
Vadim Lozin; Martin Milanič. On the Maximum Independent Set Problem in Subclasses of Planar Graphs. Journal of Graph Algorithms and Applications, Tome 14 (2010) no. 2, pp. 269-286. doi : 10.7155/jgaa.00207. http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00207/

Cité par Sources :