Ap. Punnen et Kpk. Nair, IMPROVED COMPLEXITY BOUND FOR THE MAXIMUM CARDINALITY BOTTLENECK BIPARTITE MATCHING PROBLEM, Discrete applied mathematics, 55(1), 1994, pp. 91-93
Let G(V1, V2, E) be a bipartite graph and for each edge e is-an-elemen
t-of E a weight W(e) is prescribed. Then the bottleneck bipartite matc
hing problem (BBMP) is to find a maximum cardinality matching M in G s
uch that the largest edge weight associated with M is as small as poss
ible. The best known algorithm to solve this problem has a worst-case
complexity of O(m square-root n log n), where m = \E\ and n = \V1\ + \
V2\. In this note we present an O(n square-root nm) algorithm to solve
BBMP, improving the best available bound by a factor of (square-root
m log n)/n.