Как можно оптимизировать алгоритм Куна при большом количестве вершин второй доли?

Для оптимизации алгоритма Куна при большом количестве вершин второй доли можно использовать следующие подходы:

• Модифицировать алгоритм. 1 До основного цикла найти произвольное паросочетание с помощью простого эвристического алгоритма, а затем улучшать его обычным алгоритмом Куна. 1 Это позволит сэкономить на запусках обхода в глубину из тех вершин, которые уже включены в текущее паросочетание. 1
• Использовать жадную инициализацию. 23 Например, заранее пройтись по вершинам левой доли и сматчить их со свободной вершиной правой доли, если она есть. 23
• Не заполнять нулями на каждой итерации массив used. 3 Можно хранить в нём вместо булева флага версию последнего изменения, а конкретно — номер итерации, на которой это значение стало true. 3 Если этот номер меньше текущего номера итерации, то можно воспринимать это значение как false. 3
• Использовать эвристику. 1 Например, на каждом шаге искать вершину наименьшей степени (но не изолированную), из неё выбирать любое ребро и добавлять его в паросочетание, затем удалять обе эти вершины со всеми инцидентными им рёбрами из графа. 1

Также для задач с большим количеством вершин подходит алгоритм Куна-Мункреса, который эффективно находит максимальное взвешенное паросочетание за полиномиальное время. 4