Geodesic
Polynomial-time solvability of the independent set problem in a certain class of subcubic planar graphs
Diskretnyj analiz i issledovanie operacij, Tome 24 (2017) no. 3, pp. 35-60.

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

The independent set problem for a given simple graph is to compute the size of a maximum subset of its pairwise non-adjacent vertices. In this paper we prove polynomial-time solvability of the problem for subcubic planar graphs not containing an induced tree, obtained by coinciding ends of three paths of lengths 3, 3, and 2 correspondingly. Bibliogr. 10.
Keywords: independent set problem, graph reduction
Mots-clés : efficient algorithm. 
@article{DA_2017_24_3_a2,
     author = {D. S. Malyshev and D. V. Sirotkin},
     title = {Polynomial-time solvability of the independent set problem in a certain class of subcubic planar graphs},
     journal = {Diskretnyj analiz i issledovanie operacij},
     pages = {35--60},
     publisher = {mathdoc},
     volume = {24},
     number = {3},
     year = {2017},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/DA_2017_24_3_a2/}
}
TY  - JOUR
AU  - D. S. Malyshev
AU  - D. V. Sirotkin
TI  - Polynomial-time solvability of the independent set problem in a certain class of subcubic planar graphs
JO  - Diskretnyj analiz i issledovanie operacij
PY  - 2017
SP  - 35
EP  - 60
VL  - 24
IS  - 3
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DA_2017_24_3_a2/
LA  - ru
ID  - DA_2017_24_3_a2
ER  - 
%0 Journal Article
%A D. S. Malyshev
%A D. V. Sirotkin
%T Polynomial-time solvability of the independent set problem in a certain class of subcubic planar graphs
%J Diskretnyj analiz i issledovanie operacij
%D 2017
%P 35-60
%V 24
%N 3
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DA_2017_24_3_a2/
%G ru
%F DA_2017_24_3_a2
D. S. Malyshev; D. V. Sirotkin. Polynomial-time solvability of the independent set problem in a certain class of subcubic planar graphs. Diskretnyj analiz i issledovanie operacij, Tome 24 (2017) no. 3, pp. 35-60. http://geodesic.mathdoc.fr/item/DA_2017_24_3_a2/

[1] V. E. Alekseev, “On compressible graphs”, Problems of Cybernetics, 36, Nauka, M., 1979, 23–31 (Russian)

[2] V. E. Alekseev, V. V. Lozin, “On local graph transformations preserving independence number”, Diskretn. Anal. Issled. Oper., Ser. 1, 5:1 (1998), 3–19 (Russian)

[3] V. E. Alekseev, D. S. Malyshev, “Planar graph classes with the independent set problem solvable in polynomial time”, J. Appl. Ind. Math., 3:1 (2009), 1–4 | DOI | MR

[4] D. S. Malyshev, “Classes of subcubic planar graphs for which the independent set problem is polynomially solvable”, J. Appl. Ind. Math., 7:4 (2013), 537–548 | DOI | MR | Zbl

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

[6] Alekseev V. E., Lozin V. V., Malyshev D. S., Milanič M., “The maximum independent set problem in planar graphs”, Mathematical Foundations of Computer Science 2008, Proc. 33th Int. Symp. Mathematical Foundations of Computer Science (Torun, August 25–29, 2008), Lect. Notes Comput. Sci., 5162, Springer-Verl., Heidelberg, 2008, 96–107 | DOI | MR | Zbl

[7] Hopcroft J., Tarjan R. E., “Efficient planarity testing”, J. Assoc. Comput. Machinery, 21:4 (1974), 549–568 | DOI | MR | Zbl

[8] Lozin V. V., Milanič M., “Maximum independent sets in graphs of low degree”, Proc. 18th Annu. ACM-SIAM Symp. Discrete Algorithms (New Orleans, Jan. 7-9, 2007), SIAM, Philadelphia, PA, 2007, 874–880 | MR | Zbl

[9] Lozin V. V., Milanič M., “On the maximum independent set problem in subclasses of planar graphs”, J. Graph Algorithms Appl., 14:2 (2010), 269–286 | DOI | MR | Zbl

[10] Lozin V. V., Monnot J., Ries B., “On the maximum independent set problem in subclasses of subcubic graphs”, J. Discrete Algorithms, 31 (2015), 104–112 | DOI | MR | Zbl