Алгоритм Эпштейна-Бейгеля решения задачи нахождения 3-раскраски графа
Докладчик:
Сергей Копелиович
Дата:
Monday, December 15, 2014 - 18:00
Место:
Мраморный зал ПОМИ РАН
Аннотация:
1. Оценки на смежные задачи: CSP, Vertex 3-List-Coloring, Edge 3-Coloring, 3-SAT.
2. Применение результатов для CSP и Vertex 3-Coloring для решения перечисленных задач.
3. Основная идея алгоритма. Простой результат за 1.34488^n.
4. Улучшения до 1.3289^n.
Доклад по статье: