Саша Головнёв

Алгоритмы разбиения на множества и их применения

В докладе будут рассмотрены алгоритмы решения задач покрытия и разбиения множествами. Будут рассмотрены применения алгоритма для раскраски графа, поиска domatic number. На основе полученного алгоритма будет построена экспоненциальная схема приближений для задачи о поиске хроматического числа графа.

Доклад по статье Björklund, Husfeldt, Koivisto, Set Partitioning via Inclusion–Exclusion.