Maximum bipartite matching is a fundamental problem in computer science with many applications. The HopcroftKarp algorithm can find a maximum bipartite matching of a bipartite graph G in O(√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 ℓ 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(√n(n + ℓ) 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~3n).
展开▼
机译：最大二分匹配是计算机科学中许多应用程序中的一个基本问题。 HopcroftKarp算法可以在O（√nm）时间内找到二分图G的最大二分匹配，其中n和m分别是二分图G中的节点和边的数目。 m = O（n〜2）），则Hopcroft-Karp算法的运行时间为O（n〜（2,5））。在本文中，我们考虑一个特殊情况，其中二分图G形成为ℓ个完整二分图的并集。在这种情况下，即使当G具有O（n〜2）条边时，我们也表明在O（√n（n +ℓ）log n）时间中可以找到最大二分图。我们还描述了如何将我们的解决方案应用于计算两个系统发育树的不对称中值树。我们将运行时间从O（n〜（2,5））缩短为O（n〜（1,5）log〜3n）。
展开▼
