Научная тема: «ИССЛЕДОВАНИЕ «КРИТИЧЕСКИХ» НАСЛЕДСТВЕННЫХ КЛАССОВ В АНАЛИЗЕ ВЫЧИСЛИТЕЛЬНОЙ СЛОЖНОСТИ ЗАДАЧ НА ГРАФАХ»
Специальность: 01.01.09
Год: 2014
Основные научные положения, сформулированные автором на основании проведенных исследований:
  1. Доказано, что для задач о списковом ранжировании граничные системы относительно класса лесов состоят в точности из трех конкретных классов графов.
  2. Впервые рассмотрена факторизация семейства наследственных классов по отношению равенства относительных граничных систем. Сформулирован критерий принадлежности двух наследственных классов общему классу эквивалентности по этому отношению. Показано, что при некоторых условиях граничные системы относительно объединений и пересечений двух наследственных классов выражаются через граничные системы относительно этих наследственных классов. Доказан ряд результатов о представимости и непредставимости подмножеств относительных граничных систем в виде других относительных граничных систем.
  3. Рассмотрен вопрос о единственности некоторого класса графов как граничного для задачи о независимом множестве относительно множества субкубических планар-ных графов. Эта единственность эквивалентна полиномиальной разрешимости задачи для некоторого бесконечного семейства классов графов. Установлена полиномиальная разрешимость задачи о независимом множестве для некоторого подсемейства данного семейства.
  4. Доказано, что при к > 3 для обеих задач о ^-раскраске (вершинного и реберного вариантов), для задач о хроматическом числе и индексе граничные системы являются континуальными. Тем самым показано, что для некоторых задач на графах граничные системы сложно устроены и поэтому попытки дать их полное описание, по-видимому, обречены на неудачу.
  5. Показано, что каждый граничный класс для задачи о реберной 3-раскраске является граничным и для задачи о хроматическом индексе. С другой стороны, оказалось, что при любом к > 3 существует континуум граничных классов для задачи о реберной /с-раскраске, каждый из которых не является граничным для задачи о хроматическом индексе. Доказано, что граничные системы для задач о вершинной /с-раскраске не определяют граничную систему для задачи о хроматическом числе. Именно, некоторый конкретный класс графов является граничным для задачи о хроматическом числе, но не является граничным для задачи о вершинной ^-раскраске ни при каком к.
  6. Получен критерий эффективной разрешимости задачи о реберном списковом ранжировании (задачи РСР) в некотором достаточно представительном семействе из наследственных классов графов, содержащем все конечно определенные и все минорно замкнутые классы. Из него в качестве следствия получено, что граничную систему для задачи РСР образуют ровно 10 конкретных классов графов. Это первый результат о полном описании граничных систем с момента первой публикации по граничным классам. Из полученного критерия также следует, что существует всего пять конечно определенных минимальных РСР-сложных классов и ровно один минорно замкнутый минимальный РСР-сложный класс. Все эти шесть классов явным образом описаны.
  7. Доказано достаточное условие существования минимальных сложных классов. На его основе конструктивным образом показано, что для любого натурального к есть задача на графах, имеющая ровно к минимальных сложных классов (которые удается явным образом описать). Это первые примеры полного описания минимальных сложных классов.
  8. Приведены примеры, демонстрирующие, что относительный граничный класс не всегда является граничным в абсолютном смысле и что минимальный сложный класс не всегда является граничным.
Список опубликованных работ
1. Алексеев В.Е., Малышев Д.С. Классы планарных графов с полиномиально разрешимой задачей о независимом множестве // Дискретный анализ и исследование операций. 2008. Т. 15, №1. С. 3-10 (Имеется перевод: Alekseev V.E., Malyshev D.S. Planar graph classes with the independent set problem solvable in polynomial time // Journal of Applied and Industrial Mathematics. 2009. V. 3, №1. P. 14).

2. Алексеев В.Е., Малышев Д.С. Критерий граничности и его применения // Дискретный анализ и исследование операций. 2008. Т. 15, №6. - С. 3-10.

3. Малышев Д.С. О бесконечности множества граничных классов графов в задаче о реберной 3-раскраске // Дискретный анализ и исследование операций. — 2009. — Т. 16, №1. — С. 37-43 (Имеется перевод: Malyshev D.S. On the infinity of the set of boundary classes for the edge 3-colorability problem // Journal of Applied and Industrial Mathematics. - 2010. - V. 4, №2. - P. 213-217).

4. Малышев Д.С. Граничные классы графов для некоторых задач распознавания // Дискретный анализ и исследование операций. 2009. - Т. 16, №2. - С. 85-94.

5. Малышев Д.С. Континуальные множества граничных классов графов для задач о раскраске // Дискретный анализ и исследование операций. - 2009. - Т. 16, №5. - С. 41-51.

6. Малышев Д.С. О минимальных сложных классах графов //Дискретный анализ и исследование операций. 2009. — Т. 16, №6. С. 43-51.

7. Малышев Д.С. О количестве граничных классов графов в задаче о 3-раскраске // Дискретная математика. — 2009. Т. 21, №4. — С. 129— 134 (Имеется перевод: Malyshev D.S. On the number of boundary classes in the 3-colouring problem // Discrete Mathematics and Applications. — 2010. - V. 19, №6. - P. 625-630).

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

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

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

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

12. Малышев Д.С. О пересечении и симметрической разности семейств граничных классов графов для задач о раскраске и о хроматическом числе // Дискретная математика. — 2012. — Т. 24, №2. — С. 75-78 (Имеется перевод: Malyshev D.S. On intersection and symmetric difference of families of boundary classes in the problems on colouring and on the chromatic number // Discrete Mathematics and Applications. 2011. — V. 21, №5-6. - P. 645-649).

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

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

15. Малышев Д.С. Исследование граничных классов графов для задач о раскраске // Дискретный анализ и исследование операций.

2012. - Т. 19, №6. - С. 37-48 (Имеется перевод: Malyshev D.S. A study of the boundary graph classes for colorability problems // Journal of Applied and Industrial Mathematics. 2010. V. 7, №2. P. 221 228).

16. Малышев Д.С. Экстремальные множества графов при решении задачи демаркации в семействе наследственно замкнутых классов графов // Дискретная математика. - 2012. - Т. 24, №4. - С. 91-103 (Имеется перевод: Malyshev D.S. Extremal sets of graphs in the problem of demarcation in the family of hereditary closed classes of graphs // Discrete Mathematics and Applications. 2012. V. 22, №5 6. P. 595 608).

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

18. Малышев Д.С. Расширяющие операторы для задачи о независимом множестве // Дискретный анализ и исследование операций. 2013. - Т. 20, №2. - С. 75-87 (Имеется перевод: Malyshev D.S. Expanding operators for the independent set problem // Journal of Applied and Industrial Mathematics. - 2013. - V. 7, №3. - P. 412-419)

19. Малышев Д.С. Классы субкубических планарных графов, для которых задача о независимом множестве полиномиально разрешима // Дискретный анализ и исследование операций. 2013. Т. 20, №3. С. 26-44 (Имеется перевод: Malyshev D.S. Classes of subcubic planar graphs for which the independent set problem is polynomially solvable // Journal of Applied and Industrial Mathematics. 2013. V. 7, №4. P. 475 489).

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

21. Alekseev V.E., Lozin V.V., Malyshev D.S., Milanic M. The maximum independent set problem in planar graphs // Lecture Notes in Computer Science. - 2008. - V. 5162, №4. - P. 96-107.

22. Korpelainen N., Lozin V.V., Malyshev D.S., Tiskin A. Boundary properties of graphs and algorithmic graph problems // Theoretical Computer Science. - 2011. - V. 412. - P. 3545-3554.

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