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 3, Pages 26–44 (Mi da730)  

This article is cited in 3 scientific papers (total in 3 papers)

lasses of subcubic planar graphs for which the independent set problem is polynomial-time solvable

D. S. Malyshevab

a Nizhniy Novgorod Higher School of Economics, 25/12 B. Pecherskaya St., 603155 Nizhny Novgorod, Russia
b Nizhniy Novgorod State University, 23 Gagarin Ave., 603950 Nizhniy Novgorod, Russia

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

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

English version:
Journal of Applied and Industrial Mathematics, 2013, 7:4, 537–548

Bibliographic databases:

UDC: 519.178
Received: 10.11.2011
Revised: 19.11.2012

Citation: D. S. Malyshev, “lasses of subcubic planar graphs for which the independent set problem is polynomial-time solvable”, Diskretn. Anal. Issled. Oper., 20:3 (2013), 26–44; J. Appl. Industr. Math., 7:4 (2013), 537–548

Citation in format AMSBIB
\Bibitem{Mal13}
\by D.~S.~Malyshev
\paper lasses of subcubic planar graphs for which the independent set problem is polynomial-time solvable
\jour Diskretn. Anal. Issled. Oper.
\yr 2013
\vol 20
\issue 3
\pages 26--44
\mathnet{http://mi.mathnet.ru/da730}
\mathscinet{http://www.ams.org/mathscinet-getitem?mr=3135742}
\transl
\jour J. Appl. Industr. Math.
\yr 2013
\vol 7
\issue 4
\pages 537--548
\crossref{https://doi.org/10.1134/S199047891304008X}


Linking options:
  • http://mi.mathnet.ru/eng/da730
  • http://mi.mathnet.ru/eng/da/v20/i3/p26

    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

    This publication is cited in the following articles:
    1. V. E. Alekseev, D. V. Zakharova, “Independent sets in graphs without subtrees with many leaves”, J. Appl. Industr. Math., 10:1 (2016), 1–6  mathnet  crossref  crossref  mathscinet  elib
    2. D. S. Malyshev, D. V. Sirotkin, “Polynomial-time solvability of the independent set problem in a certain class of subcubic planar graphs”, J. Appl. Industr. Math., 11:3 (2017), 400–414  mathnet  crossref  crossref  elib
    3. T. Karthick, “Independent sets in some classes of $S_{i,j,k}$-free graphs”, J. Comb. Optim., 34:2 (2017), 612–630  crossref  mathscinet  zmath  isi  scopus
  • Number of views:
    This page:273
    Full text:48
    References:34
    First page:13

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