blob: 62de72fb68b36d58980a4dcc943d2954fbe1723d (
plain) (
blame)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
|
𝓞(n³) implementation of the Hungarian algorithm,
also known as the Hungarian method, Kuhn–Munkres
algorithm or Munkres assignment.
The Hungarian algorithm solved the minmum bipartite
match problem in 𝓞(n⁴). By implementing the priority
queue with a van Emde Boas tree the time can be
reduced to 𝓞(n³ log log n). The van Emde Boas tree
is possible to use because the elements values are
bounded within the priority queue's capacity.
However this implemention achived 𝓞(n³) by not using
a priority queue.
Edmonds and Karp, and ndependently Tomizawa, has also
reduced the time complexity to 𝓞(n³), but I do not
known how.
|
