• A
  • A
  • A
  • АБВ
  • АБВ
  • АБВ
  • А
  • А
  • А
  • А
  • А
Обычная версия сайта

Исследование "критических" наследственных классов графов

2013

Изучение тех или иных классов графов уже достаточно давно составляет содержание значительной части работ по теории графов и ее приложениям. Вместе с тем, в последнее время наметился устойчивый интерес к исследованию не отдельных классов графов, а именно целых семейств классов графов, обладающих некоторым общим свойством. Одной из важнейших проблем теории графов, на решение которых направлена часть этих работ и сама постановка которых выводит на такой высокий уровень общности, является задача анализа сложности задач на графах.Общемировой интерес к этой проблеме вызван тем обстоятельством, что большинство интересных с практической и теоретической точек зрения задачи на графах являются «неподдающимися» (в теории сложности вычислений их называют NP-полными), т.е. для этих задач на настоящее время не имеется эффективных (полиномиальных) алгоритмов. Вместе с тем, известные теоретические результаты дают основания предполагать, что таких алгоритмов вообще не существует. Одним из возможных путей преодоления вычислительной сложности NP-полных задач является сужение (анализ их специальных частных случаев) путем наложения дополнительных ограничений на структуру и значения исходных данных задач. Можно с уверенностью утверждать, что изучение таких  ограничений является одной из центральных проблем современной Theoretical Computer Science. Имея какое-либо достаточно представительное семейство классов графов, можно попытаться выделить границу, до которой возможны NP-полные сужения и эффективные расширения. Данная заявка посвящена изучению этой границы для семейства наследственных классов графов, т.е. классов обыкновенных графов, замкнутых относительно удаления вершин. Данное исследование ведется на основе понятий граничного и минимального сложного классов графов, которые можно назвать «критическими» классами, поскольку они играют особую роль в анализе сложности. Полного описания «критических» классов графов не получено ни для одной задачи на графах. В рамках выполнения проекта предполагается получить такое описание для некоторой задачи, а также получить окончательные ответы на ряд других интересных мотивирующих вопросов.

Публикации по проекту:


Lozin V. V., Malyshev D. Vertex colorings of graphs with few obstructions // Discrete Applied Mathematics. 2014
Алексеев В. Е., Замараев В. А., Захарова Д. В., Малышев Д. С., Мокеев Д. Б., Сорочан С. В. Некоторые результаты о наследственных классах графов III // Вестник Нижегородского университета им. Н.И. Лобачевского. 2013. № 6(1). С. 165-172.
Малышев Д. С. Критические классы графов для задачи о реберном списковом ранжировании // Дискретный анализ и исследование операций. 2013. Т. 20. № 6. С. 59-76.
Малышев Д. С. Полиномиальная разрешимость задачи о раскраске в одном классе графов // Вестник Нижегородского университета им. Н.И. Лобачевского. 2014. Т. 3. № 1. С. 288-290.
Malyshev D. The coloring problem for classes with two small obstructions // Optimization Letters. 2014. Vol. 8. No. 8. P. 2261-2270. doi
Lozin V. V., Malyshev D. Vertex coloring of graphs with few obstructions // Discrete Applied Mathematics. 2017. Vol. 216. P. 273-280. doi