Skip to content

[Complete] 𝓞(n³) implementation of the Hungarian algorithm

License

Unknown, Unknown licenses found

Licenses found

Unknown
LICENSE
Unknown
COPYING
Notifications You must be signed in to change notification settings

maandree/hungarian-algorithm-n3

Folders and files

NameName
Last commit message
Last commit date

Latest commit

 

History

27 Commits
 
 
 
 
 
 
 
 
 
 
 
 

Repository files navigation

𝓞(n³) implementation of the Hungarian algorithm,
also known as the Hungarian method, Kuhn–Munkres
algorithm or Munkres assignment.

The Hungarian algorithm solves the minmum 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
bounded within the priority queue's capacity.
However this implemention achives 𝓞(n³) by not using
a priority queue.

Edmonds and Karp, and independently Tomizawa, has
also reduced the time complexity to 𝓞(n³), but I
do not known how.

About

[Complete] 𝓞(n³) implementation of the Hungarian algorithm

Resources

License

Unknown, Unknown licenses found

Licenses found

Unknown
LICENSE
Unknown
COPYING

Stars

Watchers

Forks

Releases

No releases published

Packages

No packages published