Hungarian algorithm (Bipartite Maximum-Weight Matching Maximum-Weight Matching)
Jump to navigation
Jump to search
Time Complexity
$O(n^{4})$
Space Complexity
$O(n^{2})$ words
(Either graph interpretation maintains O(n^2) orientations and O(n) potential or matrix interpretation manipulates an O(n)*O(n) auxiliary matrix)
Description
Approximate?
Exact
Randomized?
No, deterministic
Model of Computation
Word RAM
Year
1955
Reference
https://web.eecs.umich.edu/~pettie/matching/Kuhn-hungarian-assignment.pdf