Malyshev, Dmitriy Sergeevich

Statistics Math-Net.Ru
Total publications: 40
Scientific articles: 40
Presentations: 2

Number of views:
This page:3125
Abstract pages:10949
Full texts:1547
Associate professor
Doctor of physico-mathematical sciences (2014)
Speciality: 01.01.09 (Discrete mathematics and mathematical cybernetics)
Birth date: 29.10.1985
Keywords: graph problems, computational complexity, extremal classes.
UDC: 519.178, 519.7


Graph theory, theory of computational complexity

Main publications:
  1. Alekseev V. E., Malyshev D. S., “Klassy planarnykh grafov s polinomialno razreshimoi zadachei o nezavisimom mnozhestve”, Diskretn. analiz i issled. oper., 15:1 (2008), 3–10  mathnet
  2. Alekseev V.E., Lozin V.V., Malyshev D.S., Millanic M., “The Maximum Independent Set Problem in Planar Graphs”, Lecture Notes in Computer Science, 5162 (2008), 96–107  crossref  zmath
  3. Alekseev V. E., Malyshev D. S., “Kriterii granichnosti i ego primeneniya”, Diskretnyi analiz i issledovanie operatsii, 15:6 (2008), 3–10  mathnet
  4. Malyshev D. S., “Kontinualnye mnozhestva granichnykh klassov grafov dlya zadach o raskraske”, Diskretnyi analiz i issledovanie operatsii, 16:5 (2009), 41–51  mathnet
  5. Malyshev D. S., “O minimalnykh slozhnykh klassakh grafov”, Diskretnyi analiz i issledovanie operatsii, 16:6 (2009), 43–51  mathnet
List of publications on Google Scholar
List of publications on ZentralBlatt

Publications in Math-Net.Ru
1. D. B. Mokeev, D. S. Malyshev, “On the König graphs for a 5-path and its spanning supergraphs”, Diskretn. Anal. Issled. Oper., 27:2 (2020),  90–116  mathnet; J. Appl. Industr. Math., 14:2 (2020), 367–382  scopus
2. D. V. Gribanov, D. S. Malyshev, “Minimization of even conic functions on the two-dimensional integral lattice”, Diskretn. Anal. Issled. Oper., 27:1 (2020),  17–42  mathnet; J. Appl. Industr. Math., 14:1 (2020), 56–72  scopus
3. D. S. Taletskii, D. S. Malyshev, “Trees with a given number of leaves and the maximum number of independent sets”, Diskr. Mat., 32:2 (2020),  71–84  mathnet
4. D. S. Malyshev, “A complete classification of the complexity of the vertex 3-colourability problem for quadruples of induced 5-vertex prohibitions”, Zhurnal SVMO, 22:1 (2020),  38–47  mathnet
5. D. S. Malyshev, D. B. Mokeev, “König graphs with respect to the 4-path and its spanning supergraphs”, Diskretn. Anal. Issled. Oper., 26:1 (2019),  74–88  mathnet; J. Appl. Industr. Math., 13:1 (2019), 85–92  scopus
6. D. V. Sirotkin, D. S. Malyshev, “A constructive existence theorem related to local transformations of graphs for the independent set problem”, Zhurnal SVMO, 21:2 (2019),  215–221  mathnet  elib
7. D. V. Sirotkin, D. S. Malyshev, “On the complexity of the vertex $3$-coloring problem for the hereditary graph classes with forbidden subgraphs of small size”, Diskretn. Anal. Issled. Oper., 25:4 (2018),  112–130  mathnet  elib; J. Appl. Industr. Math., 12:4 (2018), 759–769  scopus
8. D. S. Taletskii, D. S. Malyshev, “On trees of bounded degree with maximal number of greatest independent sets”, Diskretn. Anal. Issled. Oper., 25:2 (2018),  101–123  mathnet  elib; J. Appl. Industr. Math., 12:2 (2018), 369–381  scopus
9. D. S. Taletskii, D. S. Malyshev, “Trees without twin-leaves with smallest number of maximal independent sets”, Diskr. Mat., 30:4 (2018),  115–133  mathnet  elib; Discrete Math. Appl., 30:1 (2020), 53–67  isi  scopus
10. V. E. Kruglov, D. S. Malyshev, O. V. Pochinka, “A multicolour graph as a complete topological invariant for $\Omega$-stable flows without periodic trajectories on surfaces”, Mat. Sb., 209:1 (2018),  100–126  mathnet  elib; Sb. Math., 209:1 (2018), 96–121  isi  scopus
11. D. S. Malyshev, D. V. Sirotkin, “Polynomial-time solvability of the independent set problem in a certain class of subcubic planar graphs”, Diskretn. Anal. Issled. Oper., 24:3 (2017),  35–60  mathnet  elib; J. Appl. Industr. Math., 11:3 (2017), 400–414  scopus
12. D. S. Malyshev, “Critical elements in combinatorially closed families of graph classes”, Diskretn. Anal. Issled. Oper., 24:1 (2017),  81–96  mathnet  mathscinet  elib; J. Appl. Industr. Math., 11:1 (2017), 99–106  scopus
13. D. V. sirotkin, D. S. Malyshev, “A method of graph reduction and its applications”, Diskr. Mat., 29:3 (2017),  114–125  mathnet  elib; Discrete Math. Appl., 28:4 (2018), 249–258  isi  scopus
14. D. S. Taletskii, D. S. Malyshev, “On the number of maximal independent sets in complete $q$-ary trees”, Diskr. Mat., 28:4 (2016),  139–149  mathnet  mathscinet  elib; Discrete Math. Appl., 27:5 (2017), 311–318  isi  scopus
15. D. S. Malyshev, “Complexity classification of the edge coloring problem for a family of graph classes”, Diskr. Mat., 28:2 (2016),  44–50  mathnet  mathscinet  elib; Discrete Math. Appl., 27:2 (2017), 97–101  isi  scopus
16. Vyacheslav Z. Grines, Dmitry S. Malyshev, Olga V. Pochinka, Svetlana Kh. Zinina, “Efficient Algorithms for the Recognition of Topologically Conjugate Gradient-like Diffeomorhisms”, Regul. Chaotic Dyn., 21:2 (2016),  189–203  mathnet  mathscinet  isi  scopus
17. E. Ya. Gurevich, D. S. Malyshev, “On the topological classification of Morse-Smale diffeomorphisms on the sphere $S^n$ via colored graphs”, Zhurnal SVMO, 18:4 (2016),  30–33  mathnet  elib
18. D. V. Gribanov, D. S. Malyshev, “The complexity of some graph problems with bounded minors of their constraint matrices”, Zhurnal SVMO, 18:3 (2016),  19–31  mathnet  elib
19. V. E. Kruglov, D. S. Malyshev, O. V. Pochinka, “The graph criterion for the topological equivalence of $\Omega $ – stable flows without periodic trajectories on surfaces and efficient algorithm for its application”, Zhurnal SVMO, 18:2 (2016),  47–58  mathnet  elib
20. D. S. Malyshev, “The complexity of the edge 3-colorability problem for graphs without two induced fragments each on at most six vertices”, Sib. Èlektron. Mat. Izv., 11 (2014),  811–822  mathnet
21. D. S. Malyshev, “Critical graph classes for the edge list-ranking problem”, Diskretn. Anal. Issled. Oper., 20:6 (2013),  59–76  mathnet  mathscinet; J. Appl. Industr. Math., 8:2 (2014), 245–255  scopus
22. 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  mathnet  mathscinet; J. Appl. Industr. Math., 7:4 (2013), 537–548
23. D. S. Malyshev, “Extending operators for the independent set problem”, Diskretn. Anal. Issled. Oper., 20:2 (2013),  75–87  mathnet  mathscinet; J. Appl. Industr. Math., 7:3 (2013), 412–419
24. D. S. Malyshev, “The impact of the growth rate of the packing number of graphs on the computational complexity of the independent set problem”, Diskr. Mat., 25:2 (2013),  63–67  mathnet  mathscinet  elib; Discrete Math. Appl., 23:3-4 (2013), 245–249  elib  scopus
25. D. S. Malyshev, “Study of boundary graph classes for colorability problems”, Diskretn. Anal. Issled. Oper., 19:6 (2012),  37–48  mathnet  mathscinet; J. Appl. Industr. Math., 7:2 (2013), 221–228
26. D. S. Malyshev, “Polynomial solvability of the independent set problem for one class of graphs with small diameter”, Diskretn. Anal. Issled. Oper., 19:4 (2012),  66–72  mathnet  mathscinet
27. D. S. Malyshev, “Effective solvability of the independent set problem in a class of graphs without induced path and cycle with five vertices and a big clique”, Diskretn. Anal. Issled. Oper., 19:3 (2012),  58–64  mathnet  mathscinet
28. D. S. Malyshev, “The complexity analysis of the edge-ranking problem for hereditary graph classes with at most three prohibitions”, Diskretn. Anal. Issled. Oper., 19:1 (2012),  74–96  mathnet  mathscinet
29. D. S. Malyshev, “Extremal sets of graphs in the problem of demarcation in the family of hereditary closed classes of graphs”, Diskr. Mat., 24:4 (2012),  91–103  mathnet  mathscinet  elib; Discrete Math. Appl., 22:5-6 (2012), 595–608
30. D. S. Malyshev, “On intersection and symmetric difference of families of boundary classes in the problems on colouring and on the chromatic number”, Diskr. Mat., 24:2 (2012),  75–78  mathnet  mathscinet  elib; Discrete Math. Appl., 21:5-6 (2011), 645–649
31. 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  mathnet  mathscinet  zmath
32. D. S. Malyshev, “Analysis of the number of the edges effect on the complexity of the independent set problem solvability”, Diskretn. Anal. Issled. Oper., 18:3 (2011),  84–88  mathnet  mathscinet  zmath; J. Appl. Industr. Math., 6:1 (2012), 97–99  scopus
33. D. S. Malyshev, “Minimal hard classes of graphs for the edge list-ranking problem”, Diskretn. Anal. Issled. Oper., 18:1 (2011),  70–76  mathnet  mathscinet  zmath
34. D. S. Malyshev, “On minimal hard classes of graphs”, Diskretn. Anal. Issled. Oper., 16:6 (2009),  43–51  mathnet  mathscinet  zmath
35. D. S. Malyshev, “Continued sets of boundary classes of graphs for colorability problems”, Diskretn. Anal. Issled. Oper., 16:5 (2009),  41–51  mathnet  mathscinet  zmath
36. D. S. Malyshev, “Boundary classes of graphs for some recognition problems”, Diskretn. Anal. Issled. Oper., 16:2 (2009),  85–94  mathnet  mathscinet  zmath
37. D. S. Malyshev, “On infinity of the set of boundary classes for the 3-edge-colorability problem”, Diskretn. Anal. Issled. Oper., 16:1 (2009),  37–43  mathnet  mathscinet  zmath; J. Appl. Industr. Math., 4:2 (2010), 213–217  scopus
38. D. S. Malyshev, “On the number of boundary classes in the 3-colouring problem”, Diskr. Mat., 21:4 (2009),  129–134  mathnet  mathscinet  elib; Discrete Math. Appl., 19:6 (2009), 625–630  scopus
39. V. E. Alekseev, D. S. Malyshev, “A criterion for a class of graphs to be a boundary class and applications”, Diskretn. Anal. Issled. Oper., 15:6 (2008),  3–10  mathnet  mathscinet  zmath
40. V. E. Alekseev, D. S. Malyshev, “Классы планарных графов с полиномиально разрешимой задачей о независимом множестве”, Diskretn. Anal. Issled. Oper., 15:1 (2008),  3–10  mathnet  mathscinet  zmath; J. Appl. Industr. Math., 3:1 (2009), 1–4  scopus

Presentations in Math-Net.Ru
1. Критические наследственные классы графов
D. S. Malyshev
Colloquium of the Faculty of Computer Science
June 21, 2016 18:10
2. Исследование «критических» наследственных классов в анализе вычислительной сложности задач на графах
D. S. Malyshev
MIPT Interdepartmental Seminar on Discrete Mathematics
September 25, 2013 18:30

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