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)\).
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
References
Adams III, E.N.: Consensus techniques and the comparison of taxonomic trees. Syst. Biol. 21(4), 390–397 (1972)
Bremer, K.: Combinable component consensus. Cladistics 6(4), 369–372 (1990)
Bryant, D.: A classification of consensus methods for phylogenetics. In: Janowitz, M.F., Lapointe, F.-J., McMorris, F.R., Mirkin, B., Roberts, F.S. (eds.) Bioconsensus. DIMACS Series in Discrete Mathematics and Theoretical Computer Science, vol. 61, pp. 163–184. American Mathematical Society (2003)
Cole, R., Farach-Colton, M., Hariharan, R., Przytycka, T., Thorup, M.: An o(nlog n) algorithm for the maximum agreement subtree problem for binary trees. SIAM J. Comput. 30(5), 1385–1404 (2000)
Felsenstein, J.: Inferring Phylogenies. Sinauer Associates Inc., Sunderland (2004)
Felsenstein, J.: PHYLIP, version 3.6. Software package, Department of Genome Sciences, University of Washington, Seattle, U.S.A. (2005)
Hopcroft, J.E., Karp, R.M.: An \(n^{5/2}\) algorithm for maximum matchings in bipartite graphs. SIAM J. Comput. 2(4), 225–231 (1973)
Jansson, J., Shen, C., Sung, W.-K.: Improved algorithms for constructing consensus trees. J. ACM 63(3), 1–24 (2016)
Kao, M.-Y., Lam, T.W., Sung, W.-K., Ting, H.-F.: Cavity matchings, label compressions, and unrooted evolutionary trees. SIAM J. Comput. 30(2), 602–624 (2000)
Margush, T., McMorris, F.R.: Consensus \(n\)-trees. Bull. Math. Biol. 43(2), 239–244 (1981)
Phillips, C., Warnow, T.J.: The asymmetric median tree—a new model for building consensus trees. Discrete Appl. Math. 71(1–3), 311–335 (1996)
Sokal, R.R., Rohlf, F.J.: Taxonomic congruence in the Leptopodomorpha re-examined. Syst. Zool. 30(3), 309–325 (1981)
Sung, W.-K.: Algorithms in Bioinformatics: A Practical Introduction. Chapman & Hall/CRC, Boca Raton (2010)
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2018 Springer International Publishing AG, part of Springer Nature
About this paper
Cite this paper
Rajaby, R., Sung, WK. (2018). Computing Asymmetric Median Tree of Two Trees via Better Bipartite Matching Algorithm. In: Brankovic, L., Ryan, J., Smyth, W. (eds) Combinatorial Algorithms. IWOCA 2017. Lecture Notes in Computer Science(), vol 10765. Springer, Cham. https://doi.org/10.1007/978-3-319-78825-8_29
Download citation
DOI: https://doi.org/10.1007/978-3-319-78825-8_29
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-78824-1
Online ISBN: 978-3-319-78825-8
eBook Packages: Computer ScienceComputer Science (R0)