RUS  ENG    JOURNALS   PEOPLE   ORGANISATIONS   CONFERENCES   SEMINARS   VIDEO LIBRARY   PACKAGE AMSBIB
General information
Latest issue
Archive
Impact factor
Subscription

Search papers
Search references

RSS
Latest issue
Current issues
Archive issues
What is RSS



Diskretn. Anal. Issled. Oper.:
Year:
Volume:
Issue:
Page:
Find






Personal entry:
Login:
Password:
Save password
Enter
Forgotten password?
Register


Diskretn. Anal. Issled. Oper., 2013, Volume 20, Number 2, Pages 75–87 (Mi da727)  

Extending operators for the independent set problem

D. S. Malyshevab

a Nizhniy Novgorod Higher School of Economics, Nizhniy Novgorod, Russia
b Nizhniy Novgorod State University, Nizhniy Novgorod, Russia

Abstract: 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.

Full text: PDF file (267 kB)
References: PDF file   HTML file

English version:
Journal of Applied and Industrial Mathematics, 2013, 7:3, 412–419

Bibliographic databases:

UDC: 519.178
Received: 08.02.2012
Revised: 20.04.2012

Citation: D. S. Malyshev, “Extending operators for the independent set problem”, Diskretn. Anal. Issled. Oper., 20:2 (2013), 75–87; J. Appl. Industr. Math., 7:3 (2013), 412–419

Citation in format AMSBIB
\Bibitem{Mal13}
\by D.~S.~Malyshev
\paper Extending operators for the independent set problem
\jour Diskretn. Anal. Issled. Oper.
\yr 2013
\vol 20
\issue 2
\pages 75--87
\mathnet{http://mi.mathnet.ru/da727}
\mathscinet{http://www.ams.org/mathscinet-getitem?mr=3113402}
\transl
\jour J. Appl. Industr. Math.
\yr 2013
\vol 7
\issue 3
\pages 412--419
\crossref{https://doi.org/10.1134/S1990478913030149}


Linking options:
  • http://mi.mathnet.ru/eng/da727
  • http://mi.mathnet.ru/eng/da/v20/i2/p75

    SHARE: VKontakte.ru FaceBook Twitter Mail.ru Livejournal Memori.ru


    Citing articles on Google Scholar: Russian citations, English citations
    Related articles on Google Scholar: Russian articles, English articles
  • Дискретный анализ и исследование операций
    Number of views:
    This page:180
    Full text:52
    References:22
    First page:8

     
    Contact us:
     Terms of Use  Registration  Logotypes © Steklov Mathematical Institute RAS, 2021