diff options
| author | Mattias Andrée <m@maandree.se> | 2026-02-22 13:42:13 +0100 |
|---|---|---|
| committer | Mattias Andrée <m@maandree.se> | 2026-02-22 13:42:13 +0100 |
| commit | ff2050b9e8ec451b613332aa87d357cf08b48108 (patch) | |
| tree | 3901b22b9834ac937bb82bb542c85bc293bb0c4c /README | |
| parent | Fix makefile (diff) | |
| download | hungarian-algorithm-n3-ff2050b9e8ec451b613332aa87d357cf08b48108.tar.gz hungarian-algorithm-n3-ff2050b9e8ec451b613332aa87d357cf08b48108.tar.bz2 hungarian-algorithm-n3-ff2050b9e8ec451b613332aa87d357cf08b48108.tar.xz | |
Signed-off-by: Mattias Andrée <m@maandree.se>
Diffstat (limited to 'README')
| -rw-r--r-- | README | 10 |
1 files changed, 5 insertions, 5 deletions
@@ -2,16 +2,16 @@ also known as the Hungarian method, Kuhn–Munkres algorithm or Munkres assignment. -The Hungarian algorithm solves the minmum bipartite +The Hungarian algorithm solves the minimum bipartite matching 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 +is possible to use because the element values are bounded within the priority queue's capacity. -However this implemention achives 𝓞(n³) by not using +However, this implementation achieves 𝓞(n³) by not using a priority queue. -Edmonds and Karp, and independently Tomizawa, has +Edmonds and Karp, and independently Tomizawa, have also reduced the time complexity to 𝓞(n³), but I -do not known how. +do not know how. |