{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2021,5,18]],"date-time":"2021-05-18T23:48:55Z","timestamp":1621381735025},"publisher-location":"Berlin, Heidelberg","reference-count":26,"publisher":"Springer Berlin Heidelberg","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1999]]},"DOI":"10.1007\/3-540-48481-7_38","type":"book-chapter","created":{"date-parts":[[2007,10,27]],"date-time":"2007-10-27T23:49:40Z","timestamp":1193528980000},"page":"438-449","source":"Crossref","is-referenced-by-count":13,"title":["A Decomposition Theorem for MaximumWeight Bipartite Matchings with Applications to Evolutionary Trees"],"prefix":"10.1007","author":[{"given":"Ming-Yang","family":"Kao","sequence":"first","affiliation":[]},{"given":"Tak-Wah","family":"Lam","sequence":"additional","affiliation":[]},{"given":"Wing-Kin","family":"Sung","sequence":"additional","affiliation":[]},{"given":"Hing-Fung","family":"Ting","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2003,1,14]]},"reference":[{"key":"38_CR1","doi-asserted-by":"publisher","first-page":"1216","DOI":"10.1137\/S0097539793244587","volume":"23","author":"R. Agarwala","year":"1994","unstructured":"R. Agarwala and D. Fern\u00e1ndez-Baca, A polynomial-time algorithm for the perfect phylogeny problem when the number of character states is fixed, SIAM Journal on Computing, 23 (1994), pp. 1216\u20131224.","journal-title":"SIAM Journal on Computing"},{"key":"38_CR2","series-title":"Lect Notes Comput Sci","doi-asserted-by":"crossref","first-page":"273","DOI":"10.1007\/3-540-55719-9_80","volume-title":"Proceedings of the 19th International Colloquium on Automata, Languages, and Programming","author":"H. L. Bodlaender","year":"1992","unstructured":"H. L. Bodlaender, M. R. Fellows, and T. J. Warnow, Two strikes against perfect phylogeny, in Lecture Notes in Computer Science 623: Proceedings of the 19th International Colloquium on Automata, Languages, and Programming, Springer-Verlag, New York, NY, 1992, pp. 273\u2013283."},{"key":"38_CR3","doi-asserted-by":"crossref","unstructured":"J. Bondy and U. Murty, Graph Theory with Applications, North-Holland, NewYork, NY, 1976.","DOI":"10.1007\/978-1-349-03521-2"},{"key":"38_CR4","doi-asserted-by":"publisher","first-page":"106","DOI":"10.1016\/0196-6774(87)90030-7","volume":"8","author":"M. J. Chung","year":"1987","unstructured":"M. J. Chung, O(n\n 2.5) time algorithms for the subgraph homeomorphism problem on trees, Journal of Algorithms, 8 (1987), pp. 106\u2013112.","journal-title":"Journal of Algorithms"},{"key":"38_CR5","unstructured":"R. Cole and R. Hariharan, An O(n log n) algorithm for the maximum agreement subtree problem for binary trees, in Proceedings of the 7th Annual ACM-SIAM Symposium on Discrete Algorithms, 1996, pp. 323\u2013332."},{"key":"38_CR6","volume-title":"Introduction to Algorithms","author":"T. H. Cormen","year":"1990","unstructured":"T. H. Cormen, C. L. Leiserson, and R. L. Rivest, Introduction to Algorithms, MIT Press, Cambridge, MA, 1990."},{"key":"38_CR7","series-title":"Lect Notes Comput Sci","doi-asserted-by":"crossref","first-page":"381","DOI":"10.1007\/3-540-60313-1_157","volume-title":"Proceedings of the 3rd Annual European Symposium on Algorithms","author":"M. Farach","year":"1995","unstructured":"M. Farach, T. M. Przytycka, and M. Thorup, Computing the agreement of trees with bounded degrees, in Lecture Notes in Computer Science 979: Proceedings of the 3rd Annual European Symposium on Algorithms, P. Spirakis, ed., Springer-Verlag, NewYork, NY, 1995, pp. 381\u2013393."},{"key":"38_CR8","doi-asserted-by":"publisher","first-page":"29","DOI":"10.1006\/inco.1995.1155","volume":"123","author":"M. Farach","year":"1995","unstructured":"M. Farach and M. Thorup, Fast comparison of evolutionary trees, Information and Computation, 123 (1995), pp. 29\u201337.","journal-title":"Information and Computation"},{"key":"38_CR9","doi-asserted-by":"publisher","first-page":"210","DOI":"10.1137\/S0097539794262422","volume":"26","author":"M. Farach","year":"1997","unstructured":"M. Farach and M. Thorup, Sparse dynamic programming for evolutionary-tree comparison, SIAM Journal on Computing, 26 (1997), pp. 210\u2013230.","journal-title":"SIAM Journal on Computing"},{"key":"38_CR10","doi-asserted-by":"publisher","first-page":"261","DOI":"10.1006\/jcss.1995.1065","volume":"51","author":"T. Feder","year":"1995","unstructured":"T. Feder and R. Motwani, Clique partitions, graph compression and speeding-up algorithms, Journal of Computer and System Sciences, 51 (1995), pp. 261\u2013272.","journal-title":"Journal of Computer and System Sciences"},{"key":"38_CR11","doi-asserted-by":"publisher","first-page":"255","DOI":"10.1007\/BF01908078","volume":"2","author":"C. R. Finden","year":"1985","unstructured":"C. R. Finden and A. D. Gordon, Obtaining common pruned trees, Journal of Classification, 2 (1985), pp. 255\u2013276.","journal-title":"Journal of Classification"},{"key":"38_CR12","doi-asserted-by":"publisher","first-page":"596","DOI":"10.1145\/28869.28874","volume":"34","author":"M. L. Fredman","year":"1987","unstructured":"M. L. Fredman and R. E. Tarjan, Fibonacci heaps and their uses in improved network optimization algorithms, Journal of the ACM, 34 (1987), pp. 596\u2013615.","journal-title":"Journal of the ACM"},{"key":"38_CR13","doi-asserted-by":"publisher","first-page":"148","DOI":"10.1016\/0022-0000(85)90039-X","volume":"31","author":"H. N. Gabow","year":"1985","unstructured":"H. N. Gabow, Scaling algorithms for network problems, Journal of Computer and System Sciences, 31 (1985), pp. 148\u2013168.","journal-title":"Journal of Computer and System Sciences"},{"key":"38_CR14","doi-asserted-by":"publisher","first-page":"1013","DOI":"10.1137\/0218069","volume":"18","author":"H. N. Gabow","year":"1989","unstructured":"H. N. Gabow and R. E. Tarjan, Faster scaling algorithms for network problems, SIAM Journal on Computing, 18 (1989), pp. 1013\u20131036.","journal-title":"SIAM Journal on Computing"},{"key":"38_CR15","doi-asserted-by":"publisher","first-page":"23","DOI":"10.1145\/6462.6502","volume":"18","author":"Z. Galil","year":"1986","unstructured":"Z. Galil, Efficient algorithms for finding maximum matching in graphs, ACM Computing Surveys, 18 (1986), pp. 23\u201338.","journal-title":"ACM Computing Surveys"},{"key":"38_CR16","unstructured":"A. M. H. Gerards, Matching, in Handbooks in Operations Reserach and Management Science, volume 7, M. O. Ball, T. L. Magnanti, C. L. Monma, and G. L. Nemhauser, eds., Elsevier Science, 1995, pp. 135\u2013224."},{"key":"38_CR17","doi-asserted-by":"publisher","first-page":"19","DOI":"10.1002\/net.3230210104","volume":"21","author":"D. Gusfield","year":"1991","unstructured":"D. Gusfield, Efficient algorithms for inferring evolutionary trees, Networks, 21 (1991), pp. 19\u201328.","journal-title":"Networks"},{"key":"38_CR18","doi-asserted-by":"publisher","first-page":"225","DOI":"10.1137\/0202019","volume":"2","author":"J. E. Hopcroft","year":"1973","unstructured":"J. E. Hopcroft and R. M. Karp, An n\n 5\/2\n algorithm for maximum matching in bipartite graphs, SIAM Journal on Computing, 2 (1973), pp. 225\u2013231.","journal-title":"SIAM Journal on Computing"},{"key":"38_CR19","doi-asserted-by":"publisher","first-page":"1592","DOI":"10.1137\/S0097539795283504","volume":"27","author":"M. Y. Kao","year":"1998","unstructured":"M. Y. Kao, Tree contractions and evolutionary trees, SIAM Journal on Computing, 27 (1998), pp. 1592\u20131616.","journal-title":"SIAM Journal on Computing"},{"key":"38_CR20","doi-asserted-by":"crossref","unstructured":"M. Y. Kao, T. W. Lam, T. M. Przytycka, W. K. Sung, and H. F. Ting, General techniques for comparing unrooted evolutionary trees, in Proceedings of the Twenty-Ninth AnnualACM Symposium on Theory of Computing, El Paso, Texas, 4-6 May 1997, pp. 54\u201365.","DOI":"10.1145\/258533.258550"},{"key":"38_CR21","series-title":"Lect Notes Comput Sci","doi-asserted-by":"crossref","first-page":"364","DOI":"10.1007\/3-540-63890-3_39","volume-title":"Proceedings of the 8th Annual International Symposium on Algorithms and Computation","author":"M. Y. Kao","year":"1997","unstructured":"M. Y. Kao, T. W. Lam, W. K. Sung, and H. F. Ting, All-cavity maximum matchings, in Lecture Notes in Computer Science 1350: Proceedings of the 8th Annual International Symposium on Algorithms and Computation, 1997, pp. 364\u2013373."},{"key":"38_CR22","unstructured":"M. Y. Kao, T. W. Lam, W. K. Sung, and H. F. Ting, Cavity matchings, label compressions, and unrooted evolutionary trees, 1997. Submitted for journal publication."},{"key":"38_CR23","doi-asserted-by":"publisher","first-page":"83","DOI":"10.1002\/nav.3800020109","volume":"2","author":"H. W. Kuhn","year":"1955","unstructured":"H. W. Kuhn, The Hungarian method for the assignment problem, Naval Research Logistics Quarterly, 2 (1955), pp. 83\u201397.","journal-title":"Naval Research Logistics Quarterly"},{"key":"38_CR24","first-page":"295","volume":"3","author":"T. W. Lam","year":"1996","unstructured":"T. W. Lam, W. K. Sung, and H. F. Ting, Computing the unrooted maximum agreement subtree in sub-quadratic time, Nordic Journal of Computing, 3 (1996), pp. 295\u2013322.","journal-title":"Nordic Journal of Computing"},{"key":"38_CR25","doi-asserted-by":"publisher","first-page":"77","DOI":"10.1016\/0020-0190(93)90181-8","volume":"48","author":"M. Steel","year":"1993","unstructured":"M. Steel and T. Warnow, Kaikoura tree theorems: Computing the maximum agreement subtree, Information Processing Letters, 48 (1993), pp. 77\u201382.","journal-title":"Information Processing Letters"},{"key":"38_CR26","doi-asserted-by":"publisher","first-page":"302","DOI":"10.1007\/BF01955679","volume":"16","author":"L. Wang","year":"1996","unstructured":"L. Wang, T. Jiang, and E. Lawler, Approximation algorithms for tree alignment with a given phylogeny, Algorithmica, 16 (1996), pp. 302\u2013315.","journal-title":"Algorithmica"}],"container-title":["Algorithms - ESA\u2019 99","Lecture Notes in Computer Science"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-48481-7_38","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,2,24]],"date-time":"2019-02-24T18:37:03Z","timestamp":1551033423000},"score":1,"subtitle":[],"short-title":[],"issued":{"date-parts":[[1999]]},"references-count":26,"URL":"http:\/\/dx.doi.org\/10.1007\/3-540-48481-7_38","relation":{},"ISSN":["0302-9743"],"issn-type":[{"value":"0302-9743","type":"print"}],"published":{"date-parts":[[1999]]}}}