Дмитрий Сердюк

Подсчёт количества совершенных паросочетаний

В данной лекции будет рассмотрен алгоритм для подсчета количества совершенных паросочетаний в графе на n вершинах, который использует полиномиальную память и $O^*(2^{n / 2})$ время. Ранее для этой задачи были был известен алгоритм, использующий экспоненциальную памать и $O(1.619^n)$ время (Коивисто) и алгоритм, использующий полиномиальную память и $O(1.942^n)$ время (Недерлоф). На лекции будет представлен алгоритм для подсчета хафниана матрицы над любым кольцом $R$ за $O^*(2^n)$ время.