|
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:
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
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:
-
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
-
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
-
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
-
D. S. Malyshev, “Critical graph classes for the edge list-ranking problem”, J. Appl. Industr. Math., 8:2 (2014), 245–255
-
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
|
Number of views: |
This page: | 325 | Full text: | 65 | References: | 28 | First page: | 6 |
|