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

Speaker: 
Александр Куликов
Date: 
Friday, April 4, 2014 - 18:30
Place: 
ПОМИ, ауд. 203
Abstract: 

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