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
Д. С. Малышев, Д. Б. Мокеев, “Кёниговы графы относительно 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
2.
Д. В. Сироткин, Д. С. Малышев, “Конструктивная теорема существования, ассоциированная с локальными преобразованиями графов для задачи о независимом множестве”, Журнал СВМО, 21:2 (2019), 215–221
2018
3.
Д. В. Сироткин, Д. С. Малышев, “О сложности задачи вершинной $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
4.
Д. С. Талецкий, Д. С. Малышев, “О деревьях ограниченной степени с максимальным количеством наибольших независимых множеств”, Дискретн. анализ и исслед. опер., 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
5.
Д. С. Талецкий, Д. С. Малышев, “Деревья без листьев-дубликатов с наименьшим количеством максимальных независимых множеств”, Дискрет. матем., 30:4 (2018), 115–133
6.
В. Е. Круглов, Д. С. Малышев, О. В. Починка, “Многоцветный граф как полный топологический инвариант для $\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
7.
Д. С. Малышев, Д. В. Сироткин, “Полиномиальная разрешимость задачи о независимом множестве в одном классе субкубических планарных графов”, Дискретн. анализ и исслед. опер., 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
8.
Д. С. Малышев, “Критические элементы в комбинаторно замкнутых семействах классов графов”, Дискретн. анализ и исслед. опер., 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
9.
Д. В. Сироткин, Д. С. Малышев, “Способ редукции графов и его приложения”, Дискрет. матем., 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
10.
Д. С. Талецкий, Д. С. Малышев, “О количестве максимальных независимых множеств в полных $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
11.
Д. С. Малышев, “Классификация сложности задачи о рёберной раскраске для некоторого семейства классов графов”, Дискрет. матем., 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
12.
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
13.
Е. Я. Гуревич, Д. С. Малышев, “О топологической классификации диффеоморфизмов Морса-Смейла на сфере $S^n$ посредством раскрашенного графа”, Журнал СВМО, 18:4 (2016), 30–33
14.
Д. В. Грибанов, Д. С. Малышев, “Сложность некоторых задач на графах с ограниченными минорами их матриц ограничений”, Журнал СВМО, 18:3 (2016), 19–31
15.
В. Е. Круглов, Д. С. Малышев, О. В. Починка, “Графовый критерий топологической эквивалентности $\Omega$-устойчивых потоков без периодических траекторий на поверхностях и эффективный алгоритм для его применения”, Журнал СВМО, 18:2 (2016), 47–58
2014
16.
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
17.
Д. С. Малышев, “Критические классы графов для задачи о рёберном списковом ранжировании”, Дискретн. анализ и исслед. опер., 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
18.
Д. С. Малышев, “Классы субкубических планарных графов, для которых задача о независимом множестве полиномиально разрешима”, Дискретн. анализ и исслед. опер., 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
19.
Д. С. Малышев, “Расширяющие операторы для задачи о независимом множестве”, Дискретн. анализ и исслед. опер., 20:2 (2013), 75–87; D. S. Malyshev, “Extending operators for the independent set problem”, J. Appl. Industr. Math., 7:3 (2013), 412–419
20.
Д. С. Малышев, “Влияние роста упаковочного числа графов на сложность задачи о независимом множестве”, Дискрет. матем., 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
21.
Д. С. Малышев, “Исследование граничных классов графов для задач о раскраске”, Дискретн. анализ и исслед. опер., 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
22.
Д. С. Малышев, “Полиномиальная разрешимость задачи о независимом множестве для одного класса графов малого диаметра”, Дискретн. анализ и исслед. опер., 19:4 (2012), 66–72
23.
Д. С. Малышев, “Полиномиальная разрешимость задачи о независимом множестве в классе графов без порождённых простых пути и цикла с пятью вершинами и большой клики”, Дискретн. анализ и исслед. опер., 19:3 (2012), 58–64
24.
Д. С. Малышев, “Анализ сложности задачи о рёберном списковом ранжировании для наследственных классов графов с не более чем тремя запретами”, Дискретн. анализ и исслед. опер., 19:1 (2012), 74–96
25.
Д. С. Малышев, “Экстремальные множества графов при решении задачи демаркации в семействе наследственно замкнутых классов графов”, Дискрет. матем., 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
26.
Д. С. Малышев, “О пересечении и симметрической разности семейств граничных классов для задач о раскраске и о хроматическом числе”, Дискрет. матем., 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
27.
Д. С. Малышев, В. Е. Алексеев, “Граничные классы для задач о списковом ранжировании относительно лесов”, Дискретн. анализ и исслед. опер., 18:6 (2011), 61–70
28.
Д. С. Малышев, “Анализ влияния числа рёбер в связных графах на трудоёмкость решения задачи о независимом множестве”, Дискретн. анализ и исслед. опер., 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
29.
Д. С. Малышев, “Минимальные сложные классы графов для задачи о рёберном списковом ранжировании”, Дискретн. анализ и исслед. опер., 18:1 (2011), 70–76
2009
30.
Д. С. Малышев, “О минимальных сложных классах графов”, Дискретн. анализ и исслед. опер., 16:6 (2009), 43–51
31.
Д. С. Малышев, “Континуальные множества граничных классов графов для задач о раскраске”, Дискретн. анализ и исслед. опер., 16:5 (2009), 41–51
32.
Д. С. Малышев, “Граничные классы графов для некоторых задач распознавания”, Дискретн. анализ и исслед. опер., 16:2 (2009), 85–94
33.
Д. С. Малышев, “О бесконечности множества граничных классов в задаче о рёберной 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
34.
Д. С. Малышев, “О количестве граничных классов в задаче о 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
35.
В. Е. Алексеев, Д. С. Малышев, “Критерий граничности и его применения”, Дискретн. анализ и исслед. опер., 15:6 (2008), 3–10
36.
В. Е. Алексеев, Д. С. Малышев, “Классы планарных графов с полиномиально разрешимой задачей о независимом множестве”, Дискретн. анализ и исслед. опер., 15:1 (2008), 3–10; V. E. Alekseev, D. S. Malyshev, J. Appl. Industr. Math., 3:1 (2009), 1–4
Пользовательское соглашение