IMPROVED COMPLEXITY BOUND FOR THE MAXIMUM CARDINALITY BOTTLENECK BIPARTITE MATCHING PROBLEM

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.