26.04.2018 Задача 3-раскраски при ограничениях на минимальную степень графа (Надежда Воронова)

Название: Задача 3-раскраски при ограничениях на минимальную степень графа

Время: 26 апреля, 16:30

Место: АУ, аудитория 431

Докладчик: Воронова Надя

Описание:

В прошлый раз мы рассмотрели сложность задачи 3-раскраски при ограничениях снизу на минимальную степень графа, показали, что задача остаётся сложной при mindeg > n^(1-c) для c < 1. 

В этот мы:

- Покажем алгоритм для 3-раскраски, время работы которого зависит от mindeg(G), и который при mindeg(G) > 14 работает быстрее наилучшего алгоритма для общего случая

- Рассмотрим алгоритм раскраски 3-раскрашиваемого графа в 4 цвета за 1.2535^n

Доклад по статье 

N.S.Narayanaswamy, C.R.Subramanian, 

"Dominating set based exact algorithms for 3-coloring"