Geodesic
Extending operators for the independent set problem
Diskretnyj analiz i issledovanie operacij, Tome 20 (2013) no. 2, pp. 75-87

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

The notion of an extending operator for the independent set problem is introduced. This notion is a useful tool for constructive obtaining of new cases with the effective solvability of this problem in the family of hereditary classes of graphs and is applied to hereditary parts of the set $Free(\{P_5,C_5\})$. It is proved that if for a connected graph $G$ the problem is polynomial-time solvable in the class $Free(\{P_5,C_5,G\})$, then it remains the same in the class $Free(\{P_5,C_5,G\circ\overline K_2,G\oplus K_{1,p}\})$ for any $p$. New hereditary subsets of $Free(\{P_5,C_5\})$ with the independent set problem solvable in polynomial time that are not results of application of the specified operators are found. Bibliogr. 22.
Keywords: independent set problem, theory of computational complexity, extending operator, effective algorithm. 
@article{DA_2013_20_2_a5,
     author = {D. S. Malyshev},
     title = {Extending operators for the independent set problem},
     journal = {Diskretnyj analiz i issledovanie operacij},
     pages = {75--87},
     publisher = {mathdoc},
     volume = {20},
     number = {2},
     year = {2013},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/DA_2013_20_2_a5/}
}
TY  - JOUR
AU  - D. S. Malyshev
TI  - Extending operators for the independent set problem
JO  - Diskretnyj analiz i issledovanie operacij
PY  - 2013
SP  - 75
EP  - 87
VL  - 20
IS  - 2
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DA_2013_20_2_a5/
LA  - ru
ID  - DA_2013_20_2_a5
ER  - 
%0 Journal Article
%A D. S. Malyshev
%T Extending operators for the independent set problem
%J Diskretnyj analiz i issledovanie operacij
%D 2013
%P 75-87
%V 20
%N 2
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DA_2013_20_2_a5/
%G ru
%F DA_2013_20_2_a5
D. S. Malyshev. Extending operators for the independent set problem. Diskretnyj analiz i issledovanie operacij, Tome 20 (2013) no. 2, pp. 75-87. http://geodesic.mathdoc.fr/item/DA_2013_20_2_a5/