Geodesic
Сlasses of subcubic planar graphs for which the independent set problem is polynomial-time solvable
Diskretnyj analiz i issledovanie operacij, Tome 20 (2013) no. 3, pp. 26-44.

Voir la notice de l'article provenant de la source Math-Net.Ru

Polynomial-time solvability of the independent set problem for some subclasses of subcubic planar graphs is proved. Bibliogr. 5.
Keywords: independent set problem, boundary class, computational complexity, effective algorithm. 
@article{DA_2013_20_3_a1,
     author = {D. S. Malyshev},
     title = {{\CYRS}lasses of subcubic planar graphs for which the independent set problem is polynomial-time solvable},
     journal = {Diskretnyj analiz i issledovanie operacij},
     pages = {26--44},
     publisher = {mathdoc},
     volume = {20},
     number = {3},
     year = {2013},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/DA_2013_20_3_a1/}
}
TY  - JOUR
AU  - D. S. Malyshev
TI  - Сlasses of subcubic planar graphs for which the independent set problem is polynomial-time solvable
JO  - Diskretnyj analiz i issledovanie operacij
PY  - 2013
SP  - 26
EP  - 44
VL  - 20
IS  - 3
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DA_2013_20_3_a1/
LA  - ru
ID  - DA_2013_20_3_a1
ER  - 
%0 Journal Article
%A D. S. Malyshev
%T Сlasses of subcubic planar graphs for which the independent set problem is polynomial-time solvable
%J Diskretnyj analiz i issledovanie operacij
%D 2013
%P 26-44
%V 20
%N 3
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DA_2013_20_3_a1/
%G ru
%F DA_2013_20_3_a1
D. S. Malyshev. Сlasses of subcubic planar graphs for which the independent set problem is polynomial-time solvable. Diskretnyj analiz i issledovanie operacij, Tome 20 (2013) no. 3, pp. 26-44. http://geodesic.mathdoc.fr/item/DA_2013_20_3_a1/

[1] Alekseev V. E., Malyshev D. S., “Klassy planarnykh grafov s polinomialno razreshimoi zadachei o nezavisimom mnozhestve”, Diskret. analiz i issled. operatsii, 15:1 (2008), 3–10 | MR | Zbl

[2] Malyshev D. S., “Granichnye klassy dlya zadachi o nezavisimom mnozhestve v klasse planarnykh grafov”, Vest. Nizhegorod. un-ta im. N. I. Lobachevskogo, 2007, no. 6, 165–168

[3] Alekseev V. E., “On easy and hard hereditary classes of graphs with respect to the independent set problem”, Discrete Appl. Math., 132 (2004), 17–26 | DOI | MR

[4] Alekseev V. E., Lozin V. V., Malyshev D. S., Millanic M., “The maximum independent set problem in planar graphs”, Proc. Mathematical Foundations of Computer Science (Torun, August 25–29, 2008), Lect. Notes Comput. Sci., 5162, 96–107 | DOI | MR | Zbl

[5] Lozin V. V., Millanic M., “Maximum independent sets in graphs of low degree”, Proc. ACM-SIAM Symp. Discrete Algorithms (New Orleans, January 7–9, 2007), ACM–SIAM, New Orlean, 2007, 874–880 | MR