GitHub - maandree/hungarian-algorithm-n3: [Complete] 𝓞(n³) implementation of the Hungarian algorithm

This repository has been archived by the owner on Oct 6, 2024. It is now read-only.

maandree / hungarian-algorithm-n3 Public archive

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

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

Unknown, Unknown licenses found

Licenses found

41 stars 17 forks Branches Tags Activity

Star

Notifications

Branches Tags

Name		Name	Last commit message	Last commit date
Latest commit History 27 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.