Какова временная сложность алгоритма максимального двудольного сопоставления?

Вот классическая проблема: - «Есть M претендентов на работу и N рабочих мест. У каждого претендента есть подмножество вакансий, которые его интересуют. Каждая вакансия может принять только одного кандидата, а претендент на работу может быть назначен только на один работу. Найдите распределение рабочих мест соискателям таким образом, чтобы как можно больше соискателей получили работу».

Я использую следующий код и алгоритм для решения проблемы: https://www.geeksforgeeks.org/maximum-bipartite-matching/

Какова будет временная сложность этого алгоритма?


person Shalini Tomar    schedule 09.03.2020    source источник


Ответы (1)


Согласно этой статье в Википедии, алгоритм Форда и Фулкерсона имеет сложность во время выполнения O(|E|f), где |E| — количество входных ребер. Обратите внимание, что эта граница времени выполнения зависит от оптимального значения и является псевдополиномиальной.

person Codor    schedule 09.03.2020