12.09.2017 Алгоритмы раскраски графов (Надежда Воронова)

Время: 12 сентября, 16:30
Место: ПОМИ РАН, аудитория 402
Докладчик: Воронова Надежда

Описание:

Будут рассмотрены основные задачи, связанные с раскраской графов и
алгоритмы для них:

  • жадный алгоритм для раскраски в <= maxdeg(G) + 1 цветов
  • алгоритм(ы) для 3-раскраски
  • алгоритм(ы) для нахождения хроматического числа графа
  • раскраска в O(\sqrt(n)) цветов 3-раскрашиваемого графа
  • поиск хроматического многочлена
  • сведения задач друг к другу

Доклад по Thore Husfeldt, "Graph colouring algorithms"
https://arxiv.org/pdf/1505.05825.pdf