Малышев Дмитрий Сергеевич

Место работы

Институт информационных технологий, математики и механики

Кафедра алгебры, геометрии и дискретной математики

профессор

Институт информационных технологий, математики и механики

Кафедра алгебры, геометрии и дискретной математики

ведущий научный сотрудник

Ученая степень
Доктор физико-математических наук
Ученое звание
Профессор
Дата начала работы в Университете Лобачевского: 2007
Общий стаж работы 13 лет, 9 мес.
Педагогический стаж 13 лет, 5 мес.

Общие сведения

Преподавание

Научная Работа


Образование, учёные степени и учёные звания

Высшее образование
Специальность: прикладная математика и информатика. Квалификация: математик, системный программист.

Дополнительное образование, повышение квалификации, стажировки

16.09.2019 - 06.12.2019
Переподготовка: Актуальные проблемы исследования и современные технологии преподавания математики, механики и информатики, ННГУ, 250 час., документ № 522409110710, рег номер 33-1045 от 06.12.2019

16.01.2018 - 16.01.2018
Повышение квалификации: Оказание первой помощи, ННГУ, 8 час., документ № рег. № 617 от 16.01.2018

13.03.2017 - 13.05.2017
Повышение квалификации: Электронная информационно-образовательная среда вуза, ННГУ, 72 час., документ № 522404111658 рег номер 33-888 от 13.05.2017

12.05.2015 - 12.05.2015
Повышение квалификации: Исследование операций и приложения, Национальный исследовательский университет "Высшая школа экономики", 38 час., документ № №044640, рег.номер 8.1.6.18-16/605 от 12.05.2015

13.05.2014 - 18.05.2014
Повышение квалификации: Исследование операций и приложения, Национальный исследовательский университет "Высшая школа экономики", 36 час., документ № №023487, рег номер 8.1.6.18-15/175 от 18.05.2014

03.11.2017
Повышение квалификации: Аналитика данных, Национальный исследовательский университет "Высшая школа экономики", 16 час.

Награды

Медаль Российской Академии Наук (29.12.2015, Постановление Президиум РАН)

Почетная грамота Министерства обраования Нижегородской области за достигнутые результаты

Список преподаваемых дисциплин

Институт информационных технологий, математики и механики
Алгоритмы и сложность
Анализ и разработка алгоритмов
Государственный экзамен и выпускная квалификационная работа
Математическая логика и теория алгоритмов

Институт экономики и предпринимательства
Государственный экзамен и выпускная квалификационная работа

Публикации

2021

Труды (тезисы) конференции

Alecu B., Atminas A., Lozin V.V., Malyshev D.S. Combinatorics and algorithms for quasi-chain graphs // Lecture Notes in Computer Science. Springer, 12757, 588 p.. 2021. P. 49-62.

Публикации в научных журналах

Развенская О.О., Малышев Д.С. Эффективная разрешимость задачи о взвешенной вершинной раскраске для некоторых двух наследственных классов графов // Дискретный анализ и исследование операций. № 1. Т. 28. 2021. С. 15-47.

Malyshev D.S., Razvenskaya O.O., Pardalos P.M. The computational complexity of weighted vertex coloring for {P_5,K_{2,3},K_{2,3}^+}-free graphs // Optimization Letters. № 1. V. 15. 2021. P. 137–152.

Malyshev D.S. The vertex colourability problem for {claw,butterfly}-free graphs is polynomial-time solvable // Optimization Letters. № 2. V. 15. 2021. P. 311-326.

Malyshev D.S., Morozov A.I., Pochinka O.V. Combinatorial invariant for Morse-Smale diffeomorphisms on surfaces with orientable heteroclinic // Chaos. № 2. V. 31. 2021. P. 023119.

Taletskii D.S., Malyshev D.S. Trees with a given number of leaves and the maximal number of maximum independent sets // Discrete Mathematics and Applications. № 2. V. 31. 2021. P. 135-144.

Sirotkin D.V., Malyshev D.S. On 3-сolouring of graphs with short faces and bounded maximum vertex degree // Lobachevskii Journal of Mathematics. № 4. V. 42. 2021. P. 760-766.

Razvenskaya O.O., Malyshev D.S. Efficient solvability of the weighted vertex coloring problem for some two hereditary graph classes // Journal of Applied and Industrial Mathematics. № 1. V. 15. 2021. P. 97–117.

Mokeev D.B., Malyshev D.S. On partial descriptions of König graphs for odd paths and all their spanning supergraphs // Optimization Letters. 2021. P. 1-16. [принято к печати]

2020

Публикации в научных журналах

Lozin V.V., Malyshev D.S., Mosca R., Zamaraev V.A. Independent domination versus weighted independent domination // Information Processing Letters. V. 156. 2020. P. 105914.

Malyshev D.S., Mokeev D.B. A polynomial-time algorithm of finding a minimum k-path vertex cover and a maximum k-path packing in some graphs // Optimization Letters. № 6. V. 14. 2020. P. 1317-1322.

Грибанов Д.В., Малышев Д.С. Минимизация чётных конических функций на двумерной целочисленной решётке // Дискретный анализ и исследование операций. № 1. Т. 27. 2020. С. 17-42.

Gribanov D.V., Malyshev D.S. Minimization of even conic functions on the two-dimensional integral lattice // Journal of Applied and Industrial Mathematics. № 1. V. 14. 2020. P. 56-72.

Taletskii D.S., Malyshev D.S. Trees without twin-leaves with smallest number of maximal independent sets // Discrete Mathematics and Applications. № 1. V. 30. 2020. P. 53-67.

Малышев Д.С. Полная классификация сложности задачи о вершинной 3-раскраске для четверок порожденных 5-вершинных запретов // Журнал Средневолжского математического общества. № 1. Т. 22. 2020. С. 38-47.

Малышев Д.С. Полная сложностная дихотомия для запрещенных подграфов с 7 ребрами в задаче о хроматическом индексе // Дискретный анализ и исследование операций. № 4. Т. 27. 2020. С. 104-130.

Мокеев Д.Б., Малышев Д.С. Кениговы графы относительно 5-пути и его остовных надграфов // Дискретный анализ и исследование операций. № 2. Т. 27. 2020. С. 90-116.

Талецкий Д.С., Малышев Д.С. Деревья с заданным числом листьев и максимально возможным количеством наибольших независимых множеств // Дискретная математика. № 2. Т. 32. 2020. С. 71-84.

Mokeev D.B., Malyshev D.S. On the Konig graphs for the 5-path and its spanning supergraphs // Journal of Applied and Industrial Mathematics. № 2. V. 14. 2020. P. 369-384.

Грибанов Д.В., Малышев Д.С., Мокеев Д.Б. Эффективная разрешимость задачи о взвешенной вершинной раскраске для некоторого наследственного класса графов с 5-вершинными запретами // Дискретный анализ и исследование операций. № 3. Т. 27. 2020. С. 53-70.

Gribanov D.V., Malyshev D.S., Mokeev D.B. Efficient Solvability of the Weighted Vertex Coloring Problem for Some Hereditary Class of Graphs with 5 -Vertex Prohibitions // Journal of Applied and Industrial Mathematics. V. 14. 2020. P. 480–489.

Kruglov V.E., Malyshev D.S., Pochinka O.V., Shubin D.O. On topological classification of gradient-like flows on n-sphere in sense of topological conjugacy // Regular and Chaotic Dynamics. № 6. V. 25. 2020. P. 717-729.

Grines V.Z., Gurevich E.Ya., Malyshev D.S., Pochinka O.V. On topological classification of Morse–Smale diffeomorphisms on the sphere S^n (n 3) // Nonlinearity. № 12. V. 33. 2020. P. 7088-7114.

Malyshev D.S. Complete complexity dichotomy for 7-edge forbidden subgraphs in the edge coloring problem // Journal of Applied and Industrial Mathematics. № 4. V. 14. 2020. P. 706–721.

2019

Публикации в научных журналах

Chirkov A.Yu., Gribanov D.V., Malyshev D.S., Pardalos P.M., Zolotykh N.Yu. On the complexity of quasiconvex integer minimization problem // Journal of Global Optimization. № 4. V. 73. 2019. P. 761-788.

Малышев Д.С., Мокеев Д.Б. Кениговы графы относительно 4-пути и его остовных надграфов // Дискретный анализ и исследование операций. № 26. Т. 1. 2019. С. 74-88.

Malyshev D.S., Mokeev D.B. Konig graphs with respect to the 4-path and Its spanning supergraphs // Journal of Applied and Industrial Mathematics. № 13. V. 1. 2019. P. 1-10.

Веселов С.И., Малышев Д.С., Грибанов Д.В. FPT-алгоритм вычисления ширины симплекса, заданного выпуклой оболочкой точек // Вестник Московского университета. Серия 15: Вычислительная математика и кибернетика. № 1. 2019. С. 4-14.

Veselov S.I., Gribanov D.V., Malyshev D.S. FPT-algorithm for computing the width of a simplex given by a convex hull // Moscow University Computational Mathematics and Cybernetics. № 1. V. 43. 2019. P. 1-11.

Сироткин Д.В., Малышев Д.С. Конструктивная теорема существования, ассоциированная с локальными преобразованиями графов для задачи о независимом множестве // Журнал Средневолжского математического общества. № 2. Т. 21. 2019. С. 215-221.

2018

Публикации в научных журналах

Gribanov D.V., Malyshev D.S. The computational complexity of dominating set problems for instances with bounded minors of constraint matrices // Discrete Optimization. V. 29. 2018. P. 103-110.

Gribanov D.V., Veselov S.I., Malyshev D.S., Pardalos P.M., Malyshev D.S. FPT-algorithms for some problems related to integer programming // Journal of Combinatorial Optimization. № 35. V. 4. 2018. P. 1128-1146.

Круглов Е.В., Малышев Д.С., Починка О.В. Многоцветный граф как полный топологический инвариант для Ω-устойчивых потоков без периодических траекторий на поверхностях // Математический сборник. № 1. Т. 209. 2018. С. 100-126.

Kruglov V.E., Malyshev D.S., Pochinka O.V. Topological Classification of Ω-stable Flows on Surfaces by Means of Effectively Distinguishable Multigraphs // Discrete and Continuous Dynamical Systems. № 9. V. 38. 2018. P. 4305-4327.

Malyshev D.S. The weighted coloring problem for two graph classes characterized by small forbidden induced structures // Discrete Applied Mathematics. V. 247. 2018. P. 423-432.

Malyshev D.S. A multicolour graph as a complete topological invariant for Ω-stable flows without periodic trajectories on surfaces // Sbornik: Mathematics. № 209. V. 1. 2018. P. 96-121.

Талецкий Д.С., Малышев Д.С. О деревьях ограниченной степени с максимальным количеством наибольших независимых множеств // Дискретный анализ и исследование операций. № 2. Т. 25. 2018. С. 101-123.

Сироткин Д.В., Малышев Д.С. О сложности задачи вершинной 3-раскраске для наследственных классов графов, определяемых запретами небольшого размера // Дискретный анализ и исследование операций. № 4. Т. 25. 2018. С. 112-130.

Sirotkin D.V., Malyshev D.S. A method of graph reduction and its applications // Discrete Mathematics and Applications. № 4. V. 28. 2018. P. 249-258.

Taletskii D.S., Malyshev D.S. On trees of bounded degree with maximal number of greatest independent sets // Journal of Applied and Industrial Mathematics. № 2. V. 12. 2018. P. 369-381.

Sirotkin D.V., Malyshev D.S. On the Complexity of the Vertex 3-Coloring Problem for the Hereditary Graph Classes With Forbidden Subgraphs of Small Size // Journal of Applied and Industrial Mathematics. № 4. V. 25. 2018. P. 112-130.

Талецкий Д.С., Малышев Д.С. Деревья без листьев-дубликатов с наименьшим количеством максимальных независимых множеств // Дискретная математика. № 4. Т. 30. 2018. С. 115-133.

Kruglov V.E., Malyshev D.S., Pochinka O.V. On algorithms that effectively distinguish gradient-like dynamics on surfaces // Arnold Mathematical Journal. № 3-4. V. 4. 2018. P. 483-504.

2017

Публикации в научных журналах

Malyshev D.S. Critical Elements in Combinatorially Closed Families of Graph Classes // Journal of Applied and Industrial Mathematics. № 1. V. 11. 2017. P. 99-106.

Малышев Д.С. Критические элементы в комбинаторно замкнутых семействах классов графов // Дискретный анализ и исследование операций. № 1. Т. 24. 2017. С. 81-96.

Malyshev D.S. Complexity classification of the edge coloring problem for a family of graph classes // Discrete Mathematics and Applications. № 2. V. 27. 2017. P. 97-103.

Gribanov D.V., Malyshev D.S. The computational complexity of three graph problems for instances with bounded minors of constraint matrices // Discrete Applied Mathematics. V. 227. 2017. P. 13-20.

Сироткин Д.В., Малышев Д.С. Способ редукции графов и его приложения // Дискретная математика. № 3. Т. 29. 2017. С. 114-125.

Малышев Д.С., Сироткин Д.В. Полиномиальная разрешимость задачи о независимом множестве в одном классе субкубических планарных графов // Дискретный анализ и исследование операций. № 3. Т. 24. 2017. С. 35-60.

Malyshev D.S., Sirotkin D.V. Polynomial-Time Solvability of the Independent Set Problem in a Certain Class of Subcubic Planar Graphs // Journal of Applied and Industrial Mathematics. № 3. V. 11. 2017. P. 400-414.

Malyshev D.S., Taletskii D.S. On the number of maximal independent sets in complete q-ary trees // Discrete Mathematics and Applications. № 5. V. 27. 2017. P. 311-318.

Lozin V.V., Malyshev D.S., Mosca R., Zamaraev V.A. More results on weighted independent domination // Theoretical Computer Science. V. 700. 2017. P. 63-74.

Malyshev D.S. Polynomial-time approximation algorithms for the coloring problem in some cases // Journal of Combinatorial Optimization. № 3. V. 33. 2017. P. 809-813.

Malyshev D.S. The Complexity of the Vertex 3-Colorability Problem for Some Hereditary Classes Defined By 5-Vertex Forbidden Induced Subgraphs // Graphs and Combinatorics. № 4. V. 33. 2017. P. 1009-1022.

Turkensteen M., Malyshev D.S., Goldengorin B. I., Pardalos P. M. The reduction of computation times of upper and lower tolerances for selected combinatorial optimization problems // Journal of Global Optimization. № 3. V. 68. 2017. P. 601-622.

Malyshev D.S., Lobanova O.O. Two complexity results for the vertex coloring problem // Discrete Applied Mathematics. V. 219. 2017. P. 158-166.

Lozin V.V., Malyshev D.S. Vertex coloring of graphs with few obstructions // Discrete Applied Mathematics. V. 216. 2017. P. 273-280.

2016

Публикации в научных журналах

Grinez V.Z., Malyshev D.S., Pochinka O.V., Zinina S. Kh. Efficient Algorithms for the Recognition of Topologically Conjugate Gradient-like Diffeomorhisms // Regular and Chaotic Dynamics. № 2. V. 21. 2016. P. 189-203.

Круглов В.Е., Малышев Д.С., Починка О.В. Графовый критерий топологической эквивалентности Omega-устойчивых потоков без периодических траекторий на поверхностях и эффективный алгоритм для его применения // Журнал Средневолжского математического общества. № 2. Т. 18. 2016. С. 47-58.

Малышев Д.С. Классификация сложности задачи о рёберной раскраске для некоторого семейства классов графов // Дискретная математика. № 2. Т. 28. 2016. С. 44-50.

Грибанов Д.В., Малышев Д.С. Сложность некоторых задач на графах с ограниченными минорами их матриц ограничений // Журнал Средневолжского математического общества. № 3. Т. 18. 2016. С. 19-31.

Malyshev D.S. A complexity dichotomy and a new boundary class for the dominating set problem // Journal of Combinatorial Optimization. № 1. V. 32. 2016. P. 226-243.

Malyshev D.S. A dichotomy for the dominating set problem for classes defined by small forbidden induced subgraphs // Discrete Applied Mathematics. V. 203. 2016. P. 117-126.

Malyshev D.S., Pardalos P.M. Critical hereditary graph classes: a survey // Optimization Letters. № 8. V. 10. 2016. P. 1593-1612.

Malyshev D.S. Two cases of polynomial-time solvability for the coloring problem // Journal of Combinatorial Optimization. № 2. V. 31. 2016. P. 833-845.

Талецкий Д.С., Малышев Д.С. О количестве максимальных независимых множеств в полных q-арных деревьях // Дискретная математика. № 4. Т. 28. 2016. С. 139-149.

Гуревич Е.Я., Малышев Д.С. О топологической классификации диффеоморфизмов Морса-Смейла на сфере $S^n$ посредством раскрашенного графа // Журнал Средневолжского математического общества. № 4. Т. 18. 2016. С. 30-33.

Malyshev D.S., Pochinka O.V. Description of domain structures in the Solar Corona by means multi-color graphs // Динамические системы. № 34. V. 6. 2016. P. 3-13.

2015

Публикации в научных журналах

Goldengorin B.I., Malyshev D.S., Pardalos P.M., Zamaraev V.A. A tolerance-based heuristic approach for the weighted independent set problem // Journal of Combinatorial Optimization. № 2. V. 29. 2015. P. 433-450.

Malyshev D.S. The clique problem for graphs with a few eigenvalues of the same sign // Optimization Letters. № 5. V. 9. 2015. P. 839-843.

Malyshev D.S. The complexity of the 3-colorability problem in the absence of a pair of small forbidden induced subgraphs // Discrete Mathematics. № 11. V. 338. 2015. P. 1860-1865.

2014

Публикации в научных журналах

Malyshev D.S. Boundary graph classes for some maximum induced subgraph problems // Journal of Combinatorial Optimization. № 2. V. 27. 2014. P. 345-354.

Малышев Д.С., Пардалос П.М. Эффективное вычисление допусков в задаче о взвешенном независимом множестве для некоторых классов графов // Доклады Академии наук. № 5. Т. 455. 2014. С. 529-532.

Malyshev D.S. The complexity of the edge 3-colorability problem for graphs without two induced fragments each on at most six vertices // Сибирские электронные математические известия. V. 11. 2014. P. 811-822.

Malyshev D.S. The coloring problem for classes with two small obstructions // Optimization Letters. № 8. V. 8. 2014. P. 2261-2270.

Malyshev D.S. Classes of graphs critical for the edge list-ranking problem // Journal of Applied and Industrial Mathematics. № 2. V. 8. 2014. P. 245-255.

Malyshev D.S., Pardalos P.M. Efficient Computation of Tolerances in the Weighted Independent Set Problem for Some Classes of Graphs // Doklady Mathematics. № 2. V. 89. 2014. P. 253-256.

Малышев Д.С. Полиномиальная разрешимость задачи о раскраске в одном классе графов // Вестник Нижегородского университета им. Н.И. Лобачевского. № 1. Т. 3. 2014. С. 288-290.

2013

Публикации в научных журналах

Малышев Д.С. Расширяющие операторы для задачи о независимом множестве // Дискретный анализ и исследование операций. № 2. Т. 20. 2013. С. 75-87.

Малышев Д.С. Классы субкубических планарных графов, для которых задача о независимом множестве является полиномиально разрешимой // Дискретный анализ и исследование операций. № 3. Т. 20. 2013. С. 26-44.

Малышев Д.С. Критические классы графов для задачи о реберном списковом ранжировании // Дискретный анализ и исследование операций. № 6. Т. 20. 2013. С. 59-76.

Малышев Д.С. Влияние роста упаковочного числа графов на сложность задачи о независимом множестве // Дискретная математика. № 2. Т. 25. 2013. С. 63-67.

Malyshev D.S. A Study of the Boundary Graph Classes for Colorability Problems // Journal of Applied and Industrial Mathematics. № 2. V. 7. 2013. P. 221-228.

Malyshev D.S. Expanding Operators for the Independent Set Problem // Journal of Applied and Industrial Mathematics. № 3. V. 7. 2013. P. 412-419.

Malyshev D.S. Classes of Subcubic Planar Graphs for Which the Independent Set Problem Is Polynomially Solvable // Journal of Applied and Industrial Mathematics. № 4. V. 7. 2013. P. 537-548.

Малышев Д.С. Относительные граничные классы и факторизация семейства наследственных классов графов // Вестник Нижегородского университета им. Н.И. Лобачевского. № 3. 2013. С. 181-187.

Алексеев В.Е., Замараев В.А., Захарова Д.В., Малышев Д.С., Мокеев Д.Б., Сорочан С.В. Некоторые результаты о наследственных классах графов III // Вестник Нижегородского университета им. Н.И. Лобачевского. № 6. 2013. С. 165-172.

Гольденгорин Б.И., Малышев Д.С., Пардалос П.М. Эффективное вычисление допусков в задаче о взвешенном независимом множестве для деревьев // Доклады Академии Наук. Информатика. № 4. Т. 450. 2013. С. 393-396.

Goldengorin B.I., Malyshev D.S., Pardalos P.M. Efficient Computation of Tolerances in the Weighted Independent Set Problem for Trees // Doklady Mathematics. № 3. V. 87. 2013. P. 368-371.

2012

Публикации в научных журналах

Малышев Д.С. Анализ сложности задачи о реберном списковом ранжировании для наследственных классов графов с не более чем тремя запретами // Дискретный анализ и исследование операций. № 1. Т. 19. 2012. С. 74-96.

Малышев Д.С. О связи понятий граничного и минимального сложного классов графов // Вестник Нижегородского университета им. Н.И. Лобачевского. № 2. 2012. С. 149-151.

Малышев Д.С. Полиномиальная разрешимость задачи о независимом множестве в классе графов без порожденных простых пути и цикла с пятью вершинами и большой клики // Дискретный анализ и исследование операций. № 3. Т. 19. 2012. С. 58-64.

Малышев Д.С. Полиномиальная разрешимость задачи о независимом множестве для одного класса графов малого диаметра // Дискретный анализ и исследование операций. № 4. Т. 19. 2012. С. 66-72.

Малышев Д.С. Исследование граничных классов графов для задач о раскраске // Дискретный анализ и исследование операций. № 6. Т. 19. 2012. С. 37-48.

Малышев Д.С. О пересечении и симметрической разности семейств граничных классов графов для задач о раскраске и о хроматическом числе // Дискретная математика. № 2. Т. 24. 2012. С. 75-78.

Малышев Д.С. Экстремальные множества графов при решении задачи демаркации в семействе наследственно замкнутых классов графов // Дискретная математика. № 4. Т. 24. 2012. С. 91-103.

Алексеев В.Е., Захарова Д.В., Малышев Д.С., Мокеев Д.Б., Сорочан С.В. Некоторые результаты о наследственных классах графов II // Вестник Нижегородского университета им. Н.И. Лобачевского. № 6. 2012. С. 115-120.

Malyshev D.S. Analysis of the impact of the number of edges in connected graphs on the computational complexity of the independent set problem // Journal of Applied and Industrial Mathematics. № 1. V. 6. 2012. P. 97-99.

2011

Публикации в научных журналах

Малышев Д.С. Минимальные сложные классы для задачи о реберном списковом ранжировании // Дискретный анализ и исследование операций. № 1. Т. 18. 2011. С. 70-76.

Малышев Д.С. Анализ влияния числа ребер в связных графах на трудоемкость решения задачи о независимом множестве // Дискретный анализ и исследование операций. № 3. Т. 18. 2011. С. 83-87.

Malyshev D.S., Korpeilanen N., Lozin V., Tiskin A. Boundary properties for algorithmic graph problems // Theoretical Computer Science. V. 412. 2011. P. 3545-3554.

Малышев Д.С., Алексеев В.Е., Замараев В.А., Захарова Д.В., Мокеев Д.Б. Некоторые результаты о наследственных классах графов // Вестник Нижегородского университета им. Н.И. Лобачевского. № 6. 2011. С. 169-173.

Малышев Д.С., Алексеев В.Е. Граничные классы для задач о списковом ранжировании относительно лесов // Дискретный анализ и исследование операций. № 6. Т. 18. 2011. С. 61-70.

Замараев В.А., Захарова Д.В., Малышев Д.С., Мокеев Д.Б. Некоторые результаты о наследственных классах графов // Вестник Нижегородского университета им. Н.И. Лобачевского. № 6. 2011. С. 169–173.

Алексеев В.Е., Замараев В.А., Захарова Д.В., Малышев Д.С., Мокеев Д.Б., Сорочан С.В. Некоторые результаты о наследственных классах графов I // Вестник Нижегородского университета им. Н.И. Лобачевского. № 6. 2011. С. 150-157.

©  Нижегородский государственный университет им. Н.И. Лобачевского