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

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

Описание:

Продолжение предыдущего доклада.
В этот раз будут рассмотрены:

  •  алгоритмы для нахождения хроматического числа графа
  •  алгоритм для проверки графа на 3-раскрашиваемость
  •  сведения разных задач, связанных с раскрасками, друг к другу, и

доказательство NP-полноты задачи о раскраске.

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