Improved complexity bound for the maximum cardinality bottleneck bipartite matching problem

AbstractLet G(V1, V2, E) be a bipartite graph and for each edge e ∈ E a weight We is prescribed. Then the bottleneck bipartite matching problem (BBMP) is to find a maximum cardinality matching M in G such that the largest edge weight associated with M is as small as possible. The best known algorithm to solve this problem has a worst-case complexity of O(m n log n), where m = |E| and n = |V1| + |V2|. In this note we present an O(m n log nm) algorithm to solve BBMP, improving the best available bound by a factor of O(m m log n)/n