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
К. В. Каймаков, Д. С. Малышев, “Приближенный поиск $k$-го порядкового расстояния в системе
точек единичного квадрата”, Матем. заметки, 116:4 (2024), 504–509; K. Kaymakov, D. S. Malyshev, “Approximate search for the $k$th order distance in a system of unit square points”, Math. Notes, 116:4 (2024), 646–650
2.
Н. А. Кузьмин, Д. С. Малышев, “О 5- и 6-листных деревьях, имеющих наибольшее количество паросочетаний”, Матем. заметки, 115:3 (2024), 371–384; N. A. Kuz'min, D. S. Malyshev, “On 5- and 6-Leaved Trees
with the Largest Number of Matchings”, Math. Notes, 115:3 (2024), 341–351
3.
К. В. Каймаков, Д. С. Малышев, “Эффективное вычисление всех допусков в разреженной задаче о максиминном пути”, УМН, 79:5(479) (2024), 185–186
2023
4.
Д. С. Малышев, О. И. Дугинов, “Полная сложностная дихотомия задачи о рёберной раскраске для всех множеств 8-рёберных запрещённых подграфов”, Дискретн. анализ и исслед. опер., 30:4 (2023), 91–109; D. S. Malyshev, O. I. Duginov, “A complete complexity dichotomy of the edge-coloring problem for all sets of 8-edge forbidden subgraphs”, J. Appl. Industr. Math., 17:4 (2023), 791–801
5.
Г. С. Дахно, Д. С. Малышев, “О счётном семействе граничных классов графов для задачи о доминирующем множестве”, Дискретн. анализ и исслед. опер., 30:1 (2023), 28–39
6.
Н. А. Кузьмин, Д. С. Малышев, “О деревьях диаметра 5 с максимальным количеством паросочетаний”, Матем. сб., 214:2 (2023), 143–154; N. A. Kuz'min, D. S. Malyshev, “On diameter $5$ trees with the maximum number of matchings”, Sb. Math., 214:2 (2023), 273–284
Д. С. Малышев, О. И. Дугинов, “О случаях полиномиальной разрешимости задачи о рёберной раскраске, порождаемых запрещёнными $8$-рёберными субкубическими лесами”, Дискретн. анализ и исслед. опер., 29:2 (2022), 38–61
Н. А. Кузьмин, Д. С. Малышев, “Перечисление паросочетаний в полных $q$-арных деревьях”, Матем. заметки, 111:3 (2022), 393–402; N. A. Kuz'min, D. S. Malyshev, “Enumeration of Matchings in Complete $q$-ary Trees”, Math. Notes, 111:3 (2022), 398–406
9.
Н. А. Кузьмин, Д. С. Малышев, “Новое доказательство результата о полном описании $(n,n+2)$-графов c максимальным значением индекса Хосойи”, Матем. заметки, 111:2 (2022), 258–276; N. A. Kuz'min, D. S. Malyshev, “A New Proof of a Result Concerning a Complete Description of $ (n, n + 2) $-Graphs with Maximum Value of the Hosoya Index”, Math. Notes, 111:2 (2022), 258–272
D. Gribanov, D. Malyshev, “A faster algorithm for counting the integer points number in $\Delta$-modular polyhedra”, Сиб. электрон. матем. изв., 19:2 (2022), 613–626
11.
О. И. Дугинов, Б. М. Кускова, Д. С. Малышев, Н. А. Шур, “Структурные и алгоритмические свойства максимальных диссоциирующих множеств в графах”, Тр. ИММ УрО РАН, 28:2 (2022), 114–142
2021
12.
О. О. Развенская, Д. С. Малышев, “Эффективная разрешимость задачи о взвешенной вершинной раскраске для некоторых двух наследственных классов графов”, Дискретн. анализ и исслед. опер., 28:1 (2021), 15–47; O. O. Razvenskaya, D. S. Malyshev, “Efficient solvability of the weighted vertex coloring problem for some two hereditary graph classes”, J. Appl. Industr. Math., 15:1 (2021), 97–117
Д. С. Малышев, “Полная сложностная дихотомия для запрещённых подграфов с 7 рёбрами в задаче о хроматическом индексе”, Дискретн. анализ и исслед. опер., 27:4 (2020), 104–130; D. S. Malyshev, “Complete complexity dichotomy for 7-edge forbidden subgraphs in the edge coloring problem”, J. Appl. Industr. Math., 14:4 (2020), 706–721
Д. В. Грибанов, Д. С. Малышев, Д. Б. Мокеев, “Эффективная разрешимость задачи о взвешенной вершинной раскраске для некоторого наследственного класса графов с $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
Д. Б. Мокеев, Д. С. Малышев, “Кёниговы графы относительно 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
Д. В. Грибанов, Д. С. Малышев, “Минимизация чётных конических функций на двумерной целочисленной решётке”, Дискретн. анализ и исслед. опер., 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
Д. С. Талецкий, Д. С. Малышев, “Деревья с заданным числом листьев и максимально возможным количеством наибольших независимых множеств”, Дискрет. матем., 32:2 (2020), 71–84; D. S. Taletskii, D. S. Malyshev, “Trees with a given number of leaves and the maximal number of maximum independent sets”, Discrete Math. Appl., 31:2 (2021), 135–144
18.
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
Д. С. Малышев, “Полная классификация сложности задачи о вершинной 3-раскраске для четверок порожденных 5-вершинных запретов”, Журнал СВМО, 22:1 (2020), 38–47
Д. С. Малышев, Д. Б. Мокеев, “Кёниговы графы относительно 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
Д. В. Сироткин, Д. С. Малышев, “Конструктивная теорема существования, ассоциированная с локальными преобразованиями графов для задачи о независимом множестве”, Журнал СВМО, 21:2 (2019), 215–221
2018
22.
Д. В. Сироткин, Д. С. Малышев, “О сложности задачи вершинной $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
Д. С. Талецкий, Д. С. Малышев, “О деревьях ограниченной степени с максимальным количеством наибольших независимых множеств”, Дискретн. анализ и исслед. опер., 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
Д. С. Талецкий, Д. С. Малышев, “Деревья без листьев-дубликатов с наименьшим количеством максимальных независимых множеств”, Дискрет. матем., 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
В. Е. Круглов, Д. С. Малышев, О. В. Починка, “Многоцветный граф как полный топологический инвариант для $\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
Д. С. Малышев, Д. В. Сироткин, “Полиномиальная разрешимость задачи о независимом множестве в одном классе субкубических планарных графов”, Дискретн. анализ и исслед. опер., 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
Д. С. Малышев, “Критические элементы в комбинаторно замкнутых семействах классов графов”, Дискретн. анализ и исслед. опер., 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
Д. В. Сироткин, Д. С. Малышев, “Способ редукции графов и его приложения”, Дискрет. матем., 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
Д. С. Талецкий, Д. С. Малышев, “О количестве максимальных независимых множеств в полных $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
Д. С. Малышев, “Классификация сложности задачи о рёберной раскраске для некоторого семейства классов графов”, Дискрет. матем., 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
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
Е. Я. Гуревич, Д. С. Малышев, “О топологической классификации диффеоморфизмов Морса-Смейла на сфере $S^n$ посредством раскрашенного графа”, Журнал СВМО, 18:4 (2016), 30–33
33.
Д. В. Грибанов, Д. С. Малышев, “Сложность некоторых задач на графах с ограниченными минорами их матриц ограничений”, Журнал СВМО, 18:3 (2016), 19–31
34.
В. Е. Круглов, Д. С. Малышев, О. В. Починка, “Графовый критерий топологической эквивалентности $\Omega$-устойчивых потоков без периодических траекторий на поверхностях и эффективный алгоритм для его применения”, Журнал СВМО, 18:2 (2016), 47–58
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
Д. С. Малышев, “Критические классы графов для задачи о рёберном списковом ранжировании”, Дискретн. анализ и исслед. опер., 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
Д. С. Малышев, “Классы субкубических планарных графов, для которых задача о независимом множестве полиномиально разрешима”, Дискретн. анализ и исслед. опер., 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
Д. С. Малышев, “Расширяющие операторы для задачи о независимом множестве”, Дискретн. анализ и исслед. опер., 20:2 (2013), 75–87; D. S. Malyshev, “Extending operators for the independent set problem”, J. Appl. Industr. Math., 7:3 (2013), 412–419
39.
Д. С. Малышев, “Влияние роста упаковочного числа графов на сложность задачи о независимом множестве”, Дискрет. матем., 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
Д. С. Малышев, “Исследование граничных классов графов для задач о раскраске”, Дискретн. анализ и исслед. опер., 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
Д. С. Малышев, “Полиномиальная разрешимость задачи о независимом множестве для одного класса графов малого диаметра”, Дискретн. анализ и исслед. опер., 19:4 (2012), 66–72
Д. С. Малышев, “Полиномиальная разрешимость задачи о независимом множестве в классе графов без порождённых простых пути и цикла с пятью вершинами и большой клики”, Дискретн. анализ и исслед. опер., 19:3 (2012), 58–64
Д. С. Малышев, “Анализ сложности задачи о рёберном списковом ранжировании для наследственных классов графов с не более чем тремя запретами”, Дискретн. анализ и исслед. опер., 19:1 (2012), 74–96
Д. С. Малышев, “Экстремальные множества графов при решении задачи демаркации в семействе наследственно замкнутых классов графов”, Дискрет. матем., 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
45.
Д. С. Малышев, “О пересечении и симметрической разности семейств граничных классов для задач о раскраске и о хроматическом числе”, Дискрет. матем., 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
Д. С. Малышев, В. Е. Алексеев, “Граничные классы для задач о списковом ранжировании относительно лесов”, Дискретн. анализ и исслед. опер., 18:6 (2011), 61–70
Д. С. Малышев, “Анализ влияния числа рёбер в связных графах на трудоёмкость решения задачи о независимом множестве”, Дискретн. анализ и исслед. опер., 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
Д. С. Малышев, “О бесконечности множества граничных классов в задаче о рёберной 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
Д. С. Малышев, “О количестве граничных классов в задаче о 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
В. Е. Алексеев, Д. С. Малышев, “Классы планарных графов с полиномиально разрешимой задачей о независимом множестве”, Дискретн. анализ и исслед. опер., 15:1 (2008), 3–10; V. E. Alekseev, D. S. Malyshev, J. Appl. Industr. Math., 3:1 (2009), 1–4
О. В. Анашкин, П. М. Ахметьев, Д. В. Баландин, М. К. Баринова, И. В. Бойков, А. Н. Безденежных, В. Н. Белых, П. А. Вельмисов, И. Ю. Власенко, О. Е. Галкин, С. Ю. Галкина, В. К. Горбунов, С. Д. Глызин, С. В. Гонченко, А. С. Городецкий, Е. В. Губина, Е. Я. Гуревич, А. А. Давыдов, Л. С. Ефремова, Р. В. Жалнин, А. Ю. Жиров, Е. В. Жужома, Н. И. Жукова, С. Х. Зинина, Ю. С. Ильяшенко, Н. В. Исаенкова, А. О. Казаков, А. В. Клименко, С. А. Комеч, Ю. А. Кордюков, В. Е. Круглов, Е. В. Круглов, Е. Б. Кузнецов, С. К. Ландо, Ю. А. Левченко, Л. М. Лерман, С. И. Максименко, М. И. Малкин, Д. С. Малышев, В. К. Мамаев, Т. Ф. Мамедова, В. С. Медведев, Т. В. Медведев, Д. И. Минц, Т. М. Митрякова, А. Д. Морозов, А. И. Морозов, Е. В. Ноздринова, Е. Н. Пелиновский, Я. Б. Песин, А. С. Пиковский, С. Ю. Пилюгин, Г. М. Полотовский, О. В. Починка, И. Д. Ремизов, П. Е. Рябов, А. С. Скрипченко, А. В. Слюняев, С. В. Соколов, Л. А. Сухарев, Е. А. Таланова, В. А. Тиморин, С. Б. Тихомиров, В. Ф. Тишкин, Д. В. Трещев, Д. В. Тураев, Н. Г. Чебочко, Е. Е. Чилина, П. А. Шаманаев, Д. Д. Шубин, Е. И. Яковлев, “К 75-летию Вячеслава Зигмундовича Гринеса”, Журнал СВМО, 23:4 (2021), 472–476
Обратная связь: