GitHub - JackCXY/hungarian-algorithm-n3: O(n³) implementation of the Hungarian algorithm [weird, cannot use any UCS character on this line]

JackCXY / hungarian-algorithm-n3 Public

forked from maandree/hungarian-algorithm-n3

Notifications You must be signed in to change notification settings
Fork 0
Star 0

O(n³) implementation of the Hungarian algorithm [weird, cannot use any UCS character on this line]

Unknown, Unknown licenses found

Licenses found

0 stars 18 forks Branches Tags Activity

Star

Notifications

Branches Tags

Name		Name	Last commit message	Last commit date
Latest commit History 24 Commits
.gitignore		.gitignore
COPYING		COPYING
LICENSE		LICENSE
Makefile		Makefile
README		README
hungarian.c		hungarian.c

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.