Maximum bipartite matching is a fundamental problem in computer science with many applications. The Hopcroft Karp algorithm can find a maximum bipartite matching of a bipartite graph G in O({the square root of}nm) time where n and m are the number of nodes and edges, respectively, in the bipartite graph G. However, when G is dense (i.e., m = O(n~2)), the Hopcroft-Karp algorithm runs in O(n~(2.5)) time. In this paper, we consider a special case where the bipartite graph G is formed as a union of l complete bipartite graphs. In such case, even when G has O(n~2) edges, we show that a maximum bipartite graph can be found in O({the square root of}n(n+l)log n) time. We also describe how to apply our solution to compute the asymmetric median tree of two phylogenetic trees. We improve the running time from O(n~(2.5)) to O(n~(1.5) log~3 n).
展开▼
