Graph Theory37 sections · 1633 units
Open in Course

Kuhn's Algorithm

Greedy augmenting path search

Kuhn's algorithm repeatedly finds augmenting paths until none exist. Start with an empty matching, then for each unmatched vertex in LL, try to find an augmenting path using DFS. This is distinct from the Hungarian algorithm, which solves weighted assignment problems.

This runs in O(VE)O(VE) time: you do O(V)O(V) iterations of DFS, each taking O(E)O(E) time. This is fast enough for most problems with V1000V \leq 1000.

Space complexity is O(V)O(V) for the data structures used.