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