01.01.09 (дискретная математика и математическая кибернетика)
Дата рождения:
29.10.1985
E-mail:
Ключевые слова:
задачи на графах,
вычислительная сложность,
экстремальные классы.
Коды УДК:
519.178, 519.7
Основные темы научной работы
Теория графов, теория сложности вычислений
Основные публикации:
Алексеев В. Е., Малышев Д. С., “Классы планарных графов с полиномиально разрешимой задачей о независимом множестве”, Дискретн. анализ и исслед. опер., 15:1 (2008), 3–10
Alekseev V.E., Lozin V.V., Malyshev D.S.,
Millanic М., “The Maximum Independent Set Problem in Planar Graphs”, Lecture Notes in Computer Science, 5162 (2008), 96–107
Алексеев В. Е., Малышев Д. С., “Критерий граничности и его применения”, Дискретный анализ и исследование операций, 15:6 (2008), 3–10
Малышев Д. С., “Континуальные множества граничных классов графов для задач о раскраске”, Дискретный анализ и исследование операций, 16:5 (2009), 41–51
Малышев Д. С., “О минимальных сложных классах графов”, Дискретный анализ и исследование операций, 16:6 (2009), 43–51
Д. В. Грибанов, Д. С. Малышев, Д. Б. Мокеев, “Эффективная разрешимость задачи о взвешенной вершинной раскраске для некоторого наследственного класса графов с $5$-вершинными запретами”, Дискретн. анализ и исслед. опер., 27:3 (2020), 71–87; D. V. Gribanov, D. S. Malyshev, D. B. Mokeev, “Efficient solvability of the weighted vertex coloring problem for some hereditary class of graphs with $5$-vertex prohibitions”, J. Appl. Industr. Math., 14:3 (2020), 480–489
2.
Д. Б. Мокеев, Д. С. Малышев, “Кёниговы графы относительно 5-пути и его остовных надграфов”, Дискретн. анализ и исслед. опер., 27:2 (2020), 90–116; D. B. Mokeev, D. S. Malyshev, “On the König graphs for a 5-path and its spanning supergraphs”, J. Appl. Industr. Math., 14:2 (2020), 367–382
3.
Д. В. Грибанов, Д. С. Малышев, “Минимизация чётных конических функций на двумерной целочисленной решётке”, Дискретн. анализ и исслед. опер., 27:1 (2020), 17–42; D. V. Gribanov, D. S. Malyshev, “Minimization of even conic functions on the two-dimensional integral lattice”, J. Appl. Industr. Math., 14:1 (2020), 56–72
4.
Д. С. Талецкий, Д. С. Малышев, “Деревья с заданным числом листьев и максимально возможным количеством наибольших независимых множеств”, Дискрет. матем., 32:2 (2020), 71–84
5.
Vladislav E. Kruglov, Dmitry S. Malyshev, Olga V. Pochinka, Danila D. Shubin, “On Topological Classification of Gradient-like Flows on an $n$-sphere in the Sense of Topological Conjugacy”, Regul. Chaotic Dyn., 25:6 (2020), 716–728
6.
Д. С. Малышев, “Полная классификация сложности задачи о вершинной 3-раскраске для четверок порожденных 5-вершинных запретов”, Журнал СВМО, 22:1 (2020), 38–47
2019
7.
Д. С. Малышев, Д. Б. Мокеев, “Кёниговы графы относительно 4-пути и его остовных надграфов”, Дискретн. анализ и исслед. опер., 26:1 (2019), 74–88; D. S. Malyshev, D. B. Mokeev, “König graphs with respect to the 4-path and its spanning supergraphs”, J. Appl. Industr. Math., 13:1 (2019), 85–92
8.
Д. В. Сироткин, Д. С. Малышев, “Конструктивная теорема существования, ассоциированная с локальными преобразованиями графов для задачи о независимом множестве”, Журнал СВМО, 21:2 (2019), 215–221
2018
9.
Д. В. Сироткин, Д. С. Малышев, “О сложности задачи вершинной $3$-раскраски для наследственных классов графов, определённых запретами небольшого размера”, Дискретн. анализ и исслед. опер., 25:4 (2018), 112–130; 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”, J. Appl. Industr. Math., 12:4 (2018), 759–769
10.
Д. С. Талецкий, Д. С. Малышев, “О деревьях ограниченной степени с максимальным количеством наибольших независимых множеств”, Дискретн. анализ и исслед. опер., 25:2 (2018), 101–123; D. S. Taletskii, D. S. Malyshev, “On trees of bounded degree with maximal number of greatest independent sets”, J. Appl. Industr. Math., 12:2 (2018), 369–381
11.
Д. С. Талецкий, Д. С. Малышев, “Деревья без листьев-дубликатов с наименьшим количеством максимальных независимых множеств”, Дискрет. матем., 30:4 (2018), 115–133; D. S. Taletskii, D. S. Malyshev, “Trees without twin-leaves with smallest number of maximal independent sets”, Discrete Math. Appl., 30:1 (2020), 53–67
12.
В. Е. Круглов, Д. С. Малышев, О. В. Починка, “Многоцветный граф как полный топологический инвариант для $\Omega$-устойчивых потоков без периодических траекторий на поверхностях”, Матем. сб., 209:1 (2018), 100–126; 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”, Sb. Math., 209:1 (2018), 96–121
2017
13.
Д. С. Малышев, Д. В. Сироткин, “Полиномиальная разрешимость задачи о независимом множестве в одном классе субкубических планарных графов”, Дискретн. анализ и исслед. опер., 24:3 (2017), 35–60; 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
14.
Д. С. Малышев, “Критические элементы в комбинаторно замкнутых семействах классов графов”, Дискретн. анализ и исслед. опер., 24:1 (2017), 81–96; D. S. Malyshev, “Critical elements in combinatorially closed families of graph classes”, J. Appl. Industr. Math., 11:1 (2017), 99–106
15.
Д. В. Сироткин, Д. С. Малышев, “Способ редукции графов и его приложения”, Дискрет. матем., 29:3 (2017), 114–125; D. V. sirotkin, D. S. Malyshev, “A method of graph reduction and its applications”, Discrete Math. Appl., 28:4 (2018), 249–258
2016
16.
Д. С. Талецкий, Д. С. Малышев, “О количестве максимальных независимых множеств в полных $q$-арных деревьях”, Дискрет. матем., 28:4 (2016), 139–149; D. S. Taletskii, D. S. Malyshev, “On the number of maximal independent sets in complete $q$-ary trees”, Discrete Math. Appl., 27:5 (2017), 311–318
17.
Д. С. Малышев, “Классификация сложности задачи о рёберной раскраске для некоторого семейства классов графов”, Дискрет. матем., 28:2 (2016), 44–50; D. S. Malyshev, “Complexity classification of the edge coloring problem for a family of graph classes”, Discrete Math. Appl., 27:2 (2017), 97–101
18.
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
19.
Е. Я. Гуревич, Д. С. Малышев, “О топологической классификации диффеоморфизмов Морса-Смейла на сфере $S^n$ посредством раскрашенного графа”, Журнал СВМО, 18:4 (2016), 30–33
20.
Д. В. Грибанов, Д. С. Малышев, “Сложность некоторых задач на графах с ограниченными минорами их матриц ограничений”, Журнал СВМО, 18:3 (2016), 19–31
21.
В. Е. Круглов, Д. С. Малышев, О. В. Починка, “Графовый критерий топологической эквивалентности $\Omega$-устойчивых потоков без периодических траекторий на поверхностях и эффективный алгоритм для его применения”, Журнал СВМО, 18:2 (2016), 47–58
2014
22.
D. S. Malyshev, “The complexity of the edge 3-colorability problem for graphs without two induced fragments each on at most six vertices”, Сиб. электрон. матем. изв., 11 (2014), 811–822
2013
23.
Д. С. Малышев, “Критические классы графов для задачи о рёберном списковом ранжировании”, Дискретн. анализ и исслед. опер., 20:6 (2013), 59–76; D. S. Malyshev, “Critical graph classes for the edge list-ranking problem”, J. Appl. Industr. Math., 8:2 (2014), 245–255
24.
Д. С. Малышев, “Классы субкубических планарных графов, для которых задача о независимом множестве полиномиально разрешима”, Дискретн. анализ и исслед. опер., 20:3 (2013), 26–44; D. S. Malyshev, “Сlasses of subcubic planar graphs for which the independent set problem is polynomial-time solvable”, J. Appl. Industr. Math., 7:4 (2013), 537–548
25.
Д. С. Малышев, “Расширяющие операторы для задачи о независимом множестве”, Дискретн. анализ и исслед. опер., 20:2 (2013), 75–87; D. S. Malyshev, “Extending operators for the independent set problem”, J. Appl. Industr. Math., 7:3 (2013), 412–419
26.
Д. С. Малышев, “Влияние роста упаковочного числа графов на сложность задачи о независимом множестве”, Дискрет. матем., 25:2 (2013), 63–67; D. S. Malyshev, “The impact of the growth rate of the packing number of graphs on the computational complexity of the independent set problem”, Discrete Math. Appl., 23:3-4 (2013), 245–249
2012
27.
Д. С. Малышев, “Исследование граничных классов графов для задач о раскраске”, Дискретн. анализ и исслед. опер., 19:6 (2012), 37–48; D. S. Malyshev, “Study of boundary graph classes for colorability problems”, J. Appl. Industr. Math., 7:2 (2013), 221–228
28.
Д. С. Малышев, “Полиномиальная разрешимость задачи о независимом множестве для одного класса графов малого диаметра”, Дискретн. анализ и исслед. опер., 19:4 (2012), 66–72
29.
Д. С. Малышев, “Полиномиальная разрешимость задачи о независимом множестве в классе графов без порождённых простых пути и цикла с пятью вершинами и большой клики”, Дискретн. анализ и исслед. опер., 19:3 (2012), 58–64
30.
Д. С. Малышев, “Анализ сложности задачи о рёберном списковом ранжировании для наследственных классов графов с не более чем тремя запретами”, Дискретн. анализ и исслед. опер., 19:1 (2012), 74–96
31.
Д. С. Малышев, “Экстремальные множества графов при решении задачи демаркации в семействе наследственно замкнутых классов графов”, Дискрет. матем., 24:4 (2012), 91–103; D. S. Malyshev, “Extremal sets of graphs in the problem of demarcation in the family of hereditary closed classes of graphs”, Discrete Math. Appl., 22:5-6 (2012), 595–608
32.
Д. С. Малышев, “О пересечении и симметрической разности семейств граничных классов для задач о раскраске и о хроматическом числе”, Дискрет. матем., 24:2 (2012), 75–78; D. S. Malyshev, “On intersection and symmetric difference of families of boundary classes in the problems on colouring and on the chromatic number”, Discrete Math. Appl., 21:5-6 (2011), 645–649
2011
33.
Д. С. Малышев, В. Е. Алексеев, “Граничные классы для задач о списковом ранжировании относительно лесов”, Дискретн. анализ и исслед. опер., 18:6 (2011), 61–70
34.
Д. С. Малышев, “Анализ влияния числа рёбер в связных графах на трудоёмкость решения задачи о независимом множестве”, Дискретн. анализ и исслед. опер., 18:3 (2011), 84–88; D. S. Malyshev, “Analysis of the number of the edges effect on the complexity of the independent set problem solvability”, J. Appl. Industr. Math., 6:1 (2012), 97–99
35.
Д. С. Малышев, “Минимальные сложные классы графов для задачи о рёберном списковом ранжировании”, Дискретн. анализ и исслед. опер., 18:1 (2011), 70–76
2009
36.
Д. С. Малышев, “О минимальных сложных классах графов”, Дискретн. анализ и исслед. опер., 16:6 (2009), 43–51
37.
Д. С. Малышев, “Континуальные множества граничных классов графов для задач о раскраске”, Дискретн. анализ и исслед. опер., 16:5 (2009), 41–51
38.
Д. С. Малышев, “Граничные классы графов для некоторых задач распознавания”, Дискретн. анализ и исслед. опер., 16:2 (2009), 85–94
39.
Д. С. Малышев, “О бесконечности множества граничных классов в задаче о рёберной 3-раскраске”, Дискретн. анализ и исслед. опер., 16:1 (2009), 37–43; D. S. Malyshev, “On infinity of the set of boundary classes for the 3-edge-colorability problem”, J. Appl. Industr. Math., 4:2 (2010), 213–217
40.
Д. С. Малышев, “О количестве граничных классов в задаче о 3-раскраске”, Дискрет. матем., 21:4 (2009), 129–134; D. S. Malyshev, “On the number of boundary classes in the 3-colouring problem”, Discrete Math. Appl., 19:6 (2009), 625–630
2008
41.
В. Е. Алексеев, Д. С. Малышев, “Критерий граничности и его применения”, Дискретн. анализ и исслед. опер., 15:6 (2008), 3–10
42.
В. Е. Алексеев, Д. С. Малышев, “Классы планарных графов с полиномиально разрешимой задачей о независимом множестве”, Дискретн. анализ и исслед. опер., 15:1 (2008), 3–10; V. E. Alekseev, D. S. Malyshev, J. Appl. Industr. Math., 3:1 (2009), 1–4
Пользовательское соглашение