diff options
| author | Mattias Andrée <maandree@operamail.com> | 2012-11-06 15:05:13 +0100 |
|---|---|---|
| committer | Mattias Andrée <maandree@operamail.com> | 2012-11-06 15:05:13 +0100 |
| commit | 3d9bf15464bd70403a83497cc22bcb7368aa319c (patch) | |
| tree | 1fc0f01b4cb0c8c0cb6039ec73d4e8275b55d72f /README | |
| parent | the code (diff) | |
| download | hungarian-algorithm-n3-3d9bf15464bd70403a83497cc22bcb7368aa319c.tar.gz hungarian-algorithm-n3-3d9bf15464bd70403a83497cc22bcb7368aa319c.tar.bz2 hungarian-algorithm-n3-3d9bf15464bd70403a83497cc22bcb7368aa319c.tar.xz | |
extend the readme
Diffstat (limited to '')
| -rw-r--r-- | README | 9 |
1 files changed, 9 insertions, 0 deletions
@@ -1,3 +1,12 @@ 𝓞(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. |