Лаборатория алгоритмических методов

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

Дата:

Friday, April 4, 2014 - 18:30

Аннотация:

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