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

Название: Задача 3-раскраски при ограничениях на минимальную степень графа
Время: 19 апреля, 18:30
Место: АУ, аудитория 431
Докладчик: Воронова Надежда
 
Описание:
 
Рассмотрим, как ведёт себя задача 3-раскраски при ограничениях снизу на минимальную степень графа.
- Покажем алгоритм для 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"