From 3d9bf15464bd70403a83497cc22bcb7368aa319c Mon Sep 17 00:00:00 2001 From: Mattias Andrée Date: Tue, 6 Nov 2012 15:05:13 +0100 Subject: extend the readme --- README | 9 +++++++++ 1 file changed, 9 insertions(+) (limited to 'README') diff --git a/README b/README index 7d16e7c..192d9ca 100644 --- a/README +++ b/README @@ -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. -- cgit v1.2.3-70-g09d2