Чётность гамильтоновых циклов

Докладчик: 
Александр Куликов
Дата: 
Friday, April 4, 2014 - 18:30
Место: 
ПОМИ, ауд. 203
Аннотация: 

Будет рассказан недавний алгоритм подсчёта чётности гамильтновых циклов в ориентированных графах быстрее полного перебора (напомним, что мы на данный момент не умеем проверять, есть ли в орграфе гамильтонов цикл за 1,99^n, а вот чётность числа таких циклов, как выясняется, находить умеем).