Anzeige
Erschienen in:
2018 | OriginalPaper | Buchkapitel
Computing Asymmetric Median Tree of Two Trees via Better Bipartite Matching Algorithm
verfasst von : Ramesh Rajaby, Wing-Kin Sung
Erschienen in: Combinatorial Algorithms
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
Abstract
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(\sqrt{n} m)\) 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 \(\ell \) 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(\sqrt{n} (n + \ell ) \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)\).