RUS  ENG JOURNALS   PEOPLE   ORGANISATIONS   CONFERENCES   SEMINARS   VIDEO LIBRARY   PERSONAL OFFICE
General information
Latest issue
Archive
Impact factor

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., 2011, Volume 18, Number 6, Pages 61–70 (Mi da670)  
This article is cited in 5 scientific papers (total in 5 papers)

Boundary classes for the list-ranking problems in subclasses of forests

D. S. Malysheva, V. E. Alekseevb

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

Abstract: All boundary classes are found for the graph list-ranking problems (vertex and edge variants) relative to the class of forests. It allows to determine the complexity status of these problems for any hereditary class defined by a finite set of forbidden subgraphs under the class of forests. Bibliogr. 9.

Keywords: computational complexity, boundary class, relative boundary class, list-ranking problem, forest.

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

Bibliographic databases:

Document Type: Article
UDC: 519.178
Received: 19.01.2011
Revised: 09.08.2011

Citation: D. S. Malyshev, V. E. Alekseev, “Boundary classes for the list-ranking problems in subclasses of forests”, Diskretn. Anal. Issled. Oper., 18:6 (2011), 61–70

Citation in format AMSBIB
\Bibitem{MalAle11}
\by D.~S.~Malyshev, V.~E.~Alekseev
\paper Boundary classes for the list-ranking problems in subclasses of forests
\jour Diskretn. Anal. Issled. Oper.
\yr 2011
\vol 18
\issue 6
\pages 61--70
\mathnet{http://mi.mathnet.ru/da670}
\mathscinet{http://www.ams.org/mathscinet-getitem?mr=2953800}
\zmath{https://zbmath.org/?q=an:1249.05369}


Linking options:
  • http://mi.mathnet.ru/eng/da670
  • http://mi.mathnet.ru/eng/da/v18/i6/p61

    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. D. S. Malyshev, “Analiz slozhnosti zadachi o rëbernom spiskovom ranzhirovanii dlya nasledstvennykh klassov grafov s ne bolee chem tremya zapretami”, Diskretn. analiz i issled. oper., 19:1 (2012), 74–96  mathnet  mathscinet
    2. Malyshev D.S., “O svyazi ponyatii granichnogo i minimalnogo slozhnogo klassov grafov”, Vestnik Nizhegorodskogo universiteta im. N.I. Lobachevskogo, 2012, no. 2-1, 149–151  elib
    3. Alekseev V.E., Zakharova D.V., Malyshev D.S., Mokeev D.B., Sorochan S.V., “Nekotorye rezultaty o nasledstvennykh klassakh grafov. ii”, Vestnik nizhegorodskogo universiteta im. N.I. Lobachevskogo, 2012, 115–120  elib
    4. D. S. Malyshev, “Critical graph classes for the edge list-ranking problem”, J. Appl. Industr. Math., 8:2 (2014), 245–255  mathnet  crossref  mathscinet
    5. D. S. Malyshev, “The complexity of the edge 3-colorability problem for graphs without two induced fragments each on at most six vertices”, Sib. elektron. matem. izv., 11 (2014), 811–822  mathnet
    		• Дискретный анализ и исследование операций
    Number of views:
    This page:229
    Full text:37
    References:15
    First page:6
     
    Contact us:
    		  Terms of Use  Registration  Logotypes © Steklov Mathematical Institute RAS, 2018