Geodesic
Effective solvability of the independent set problem in a~class of graphs without induced path and cycle with five vertices and a~big clique
Diskretnyj analiz i issledovanie operacij, Tome 19 (2012) no. 3, pp. 58-64.

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

An algorithm for finding the independence number of a $n$-vertex graph from the class $\operatorname{Free}(\{P_5,C_5,K_p\})$ in time $O(n^{p+O(1)})$ is proposed. Bibliogr. 10.
Keywords: the independent set problem, computational complexity
Mots-clés : polynomial algorithm. 
@article{DA_2012_19_3_a4,
     author = {D. S. Malyshev},
     title = {Effective solvability of the independent set problem in a~class of graphs without induced path and cycle with five vertices and a~big clique},
     journal = {Diskretnyj analiz i issledovanie operacij},
     pages = {58--64},
     publisher = {mathdoc},
     volume = {19},
     number = {3},
     year = {2012},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/DA_2012_19_3_a4/}
}
TY  - JOUR
AU  - D. S. Malyshev
TI  - Effective solvability of the independent set problem in a~class of graphs without induced path and cycle with five vertices and a~big clique
JO  - Diskretnyj analiz i issledovanie operacij
PY  - 2012
SP  - 58
EP  - 64
VL  - 19
IS  - 3
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DA_2012_19_3_a4/
LA  - ru
ID  - DA_2012_19_3_a4
ER  - 
%0 Journal Article
%A D. S. Malyshev
%T Effective solvability of the independent set problem in a~class of graphs without induced path and cycle with five vertices and a~big clique
%J Diskretnyj analiz i issledovanie operacij
%D 2012
%P 58-64
%V 19
%N 3
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DA_2012_19_3_a4/
%G ru
%F DA_2012_19_3_a4
D. S. Malyshev. Effective solvability of the independent set problem in a~class of graphs without induced path and cycle with five vertices and a~big clique. Diskretnyj analiz i issledovanie operacij, Tome 19 (2012) no. 3, pp. 58-64. http://geodesic.mathdoc.fr/item/DA_2012_19_3_a4/

[1] Alekseev V. E., Talanov V. A., Grafy i algoritmy. Struktury dannykh. Modeli vychislenii, Izd-vo “INTUIT.ru”, M., 2006, 320 pp.

[2] Arbib C., Mosca R., “On $(P_5, diamond)$-free graphs”, Discrete Math., 250 (2002), 1–22 | DOI | MR | Zbl

[3] Brandstadt A., Mosca R., “On the structure and stability number of $P_5$- and co-chair-free graphs”, Discrete Appl. Math., 132 (2003), 47–65 | DOI | MR

[4] Brandstadt A., Le H.-O., Mosca R., “Chordal co-gem-free and $(P_5, gem)$-free graphs have bounded clique-width”, Discrete Appl. Math., 145:2 (2005), 232–241 | DOI | MR

[5] Lozin V., Mosca R., “Maximum independent sets in subclasses of $P_5$-free graphs”, Inf. Process. Lett., 109:6 (2009), 319–324 | DOI | MR | Zbl

[6] Mosca R., “Polynomial algorithms for the maximum stable set problem on particular classes of $P_5$-free graphs”, Inf. Process. Lett., 61:3 (1997), 137–143 | DOI | MR

[7] Mosca R., “Stable sets in certain $P_6$-free graphs”, Discrete Appl. Math., 92 (1999), 177–191 | DOI | MR | Zbl

[8] Mosca R., “Some results on maximum stable sets in certain $P_5$-free graphs”, Discrete Appl. Math., 132 (2003), 175–183 | DOI | MR | Zbl

[9] Mosca R., “Some observations on maximum weight stable sets in certain $P$”, Eur. J. Oper. Res., 184:3 (2008), 849–859 | DOI | MR | Zbl

[10] Simone C. D., Mosca R., “Stable set and clique polytopes of $(P_5,gem)$-free graphs”, Discrete Math., 307:22 (2007), 2661–2670 | DOI | MR | Zbl