Особенности применения алгоритма Куна для решения задач паросочетания:

• Инкрементальное построение максимального паросочетания. 2 Алгоритм начинается с пустого паросочетания и на каждом шаге ищет увеличивающую цепь и проводит её чередование. 2
• Поиск увеличивающей цепи. 25 Для этого мысленно строят граф, в котором из правой доли в левую можно идти только по рёбрам паросочетания, а из левой в правую — по любым. 2 Затем запускают поиск любого пути из свободной вершины левой доли в какую-нибудь свободную вершину правой доли в изменённом графе, и ровно такой путь и будет увеличивающим. 2
• Оптимизации для увеличения производительности. 2 Например, паросочетание можно жадно инициализировать или не заполнять нулями на каждой итерации вспомогательный массив, а хранить в нём версию последнего изменения. 2

Алгоритм Куна выгоднее всего использовать, когда количество вершин в левой доле двудольного графа сильно меньше, чем в правой. 1