{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,5]],"date-time":"2024-09-05T13:47:40Z","timestamp":1725544060583},"publisher-location":"Berlin, Heidelberg","reference-count":14,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540354550"},{"type":"electronic","value":"9783540354611"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2006]]},"DOI":"10.1007\/11780441_16","type":"book-chapter","created":{"date-parts":[[2006,6,30]],"date-time":"2006-06-30T15:02:51Z","timestamp":1151679771000},"page":"165-176","source":"Crossref","is-referenced-by-count":4,"title":["Solving the Maximum Agreement SubTree and the Maximum Compatible Tree Problems on Many Bounded Degree Trees"],"prefix":"10.1007","author":[{"given":"Sylvain","family":"Guillemot","sequence":"first","affiliation":[]},{"given":"Fran\u00e7ois","family":"Nicolas","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"issue":"6","key":"16_CR1","doi-asserted-by":"publisher","first-page":"1656","DOI":"10.1137\/S0097539794269461","volume":"26","author":"A. Amir","year":"1997","unstructured":"Amir, A., Keselman, D.: Maximum agreement subtree in a set of evolutionary trees: metrics and efficient algorithm. SIAM Journal on Computing\u00a026(6), 1656\u20131669 (1997)","journal-title":"SIAM Journal on Computing"},{"key":"16_CR2","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"205","DOI":"10.1007\/978-3-540-27801-6_15","volume-title":"Combinatorial Pattern Matching","author":"V. Berry","year":"2004","unstructured":"Berry, V., Nicolas, F.: Maximum agreement and compatible supertrees. In: Sahinalp, S.C., Muthukrishnan, S., Dogrusoz, U. (eds.) CPM 2004. LNCS, vol.\u00a03109, pp. 205\u2013219. Springer, Heidelberg (2004)"},{"key":"16_CR3","unstructured":"Bryant, D.: Building trees, hunting for trees and comparing trees: theory and method in phylogenetic analysis. PhD thesis, University of Canterbury, Department of Mathemathics (1997)"},{"key":"16_CR4","doi-asserted-by":"publisher","first-page":"212","DOI":"10.1145\/1007352.1007391","volume-title":"Proceedings of the 36th Annual ACM Symposium on Theory of Computing (STOC 2004)","author":"J. Chen","year":"2004","unstructured":"Chen, J., Huang, X., Kanj, I.A., Xia, G.: Linear FPT reductions and computational lower bounds. In: Babai, L. (ed.) Proceedings of the 36th Annual ACM Symposium on Theory of Computing (STOC 2004), pp. 212\u2013221. ACM Press, New York (2004)"},{"key":"16_CR5","series-title":"Monographs in Computer Science","doi-asserted-by":"crossref","DOI":"10.1007\/978-1-4612-0515-9","volume-title":"Parameterized Complexity","author":"R.G. Downey","year":"1999","unstructured":"Downey, R.G., Fellows, M.R.: Parameterized Complexity. Monographs in Computer Science. Springer, Heidelberg (1999)"},{"issue":"6","key":"16_CR6","doi-asserted-by":"publisher","first-page":"297","DOI":"10.1016\/0020-0190(95)00110-X","volume":"55","author":"M. Farach","year":"1995","unstructured":"Farach, M., Przytycka, T.M., Thorup, M.: On the agreement of many trees. Information Processing Letters\u00a055(6), 297\u2013301 (1995)","journal-title":"Information Processing Letters"},{"key":"16_CR7","doi-asserted-by":"publisher","first-page":"255","DOI":"10.1007\/BF01908078","volume":"2","author":"C.R. Finden","year":"1985","unstructured":"Finden, C.R., Gordon, A.D.: Obtaining common pruned trees. Journal of Classification\u00a02, 255\u2013276 (1985)","journal-title":"Journal of Classification"},{"key":"16_CR8","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"156","DOI":"10.1007\/3-540-44696-6_12","volume-title":"Algorithms in Bioinformatics","author":"G. Ganapathysaravanabavan","year":"2001","unstructured":"Ganapathysaravanabavan, G., Warnow, T.J.: Finding a maximum compatible tree for a bounded number of trees with bounded degree is solvable in polynomial time. In: Gascuel, O., Moret, B.M.E. (eds.) WABI 2001. LNCS, vol.\u00a02149, pp. 156\u2013163. Springer, Heidelberg (2001)"},{"issue":"2","key":"16_CR9","doi-asserted-by":"publisher","first-page":"55","DOI":"10.1016\/0893-9659(96)00012-2","volume":"9","author":"A.M. Hamel","year":"1996","unstructured":"Hamel, A.M., Steel, M.A.: Finding a maximum compatible tree is NP-hard for sequences and trees. Applied Mathematics Letters\u00a09(2), 55\u201359 (1996)","journal-title":"Applied Mathematics Letters"},{"issue":"1\u20133","key":"16_CR10","doi-asserted-by":"publisher","first-page":"153","DOI":"10.1016\/S0166-218X(96)00062-5","volume":"71","author":"J. Hein","year":"1996","unstructured":"Hein, J., Jiang, T., Wang, L., Zhang, K.: On the complexity of comparing evolutionary trees. Discrete Applied Mathematics\u00a071(1\u20133), 153\u2013169 (1996)","journal-title":"Discrete Applied Mathematics"},{"issue":"4","key":"16_CR11","doi-asserted-by":"publisher","first-page":"512","DOI":"10.1006\/jcss.2001.1774","volume":"63","author":"R. Impagliazzo","year":"2001","unstructured":"Impagliazzo, R., Paturi, R., Zane, F.: Which problems have strongly exponential complexity? Journal of Computer and System Sciences\u00a063(4), 512\u2013530 (2001)","journal-title":"Journal of Computer and System Sciences"},{"issue":"2","key":"16_CR12","doi-asserted-by":"publisher","first-page":"212","DOI":"10.1006\/jagm.2001.1163","volume":"40","author":"M.-Y. Kao","year":"2001","unstructured":"Kao, M.-Y., Lam, T.W., Sung, W.-K., Ting, H.-F.: An even faster and more unifying algorithm for comparing trees via unbalanced bipartite matchings. Journal of Algorithms\u00a040(2), 212\u2013233 (2001)","journal-title":"Journal of Algorithms"},{"issue":"3","key":"16_CR13","doi-asserted-by":"publisher","first-page":"425","DOI":"10.1016\/0022-0000(91)90023-X","volume":"43","author":"C.H. Papadimitriou","year":"1991","unstructured":"Papadimitriou, C.H., Yannakakis, M.: Optimization, approximation, and complexity classes. Journal of Computer and System Sciences\u00a043(3), 425\u2013440 (1991)","journal-title":"Journal of Computer and System Sciences"},{"issue":"4","key":"16_CR14","doi-asserted-by":"publisher","first-page":"757","DOI":"10.1016\/S0022-0000(03)00078-3","volume":"67","author":"K. Pietrzak","year":"2003","unstructured":"Pietrzak, K.: On the parameterized complexity of the fixed alphabet shortest common supersequence and longest common subsequence problems. Journal of Computer and System Sciences\u00a067(4), 757\u2013771 (2003)","journal-title":"Journal of Computer and System Sciences"}],"container-title":["Lecture Notes in Computer Science","Combinatorial Pattern Matching"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/11780441_16.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,4,27]],"date-time":"2021-04-27T07:16:13Z","timestamp":1619507773000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/11780441_16"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2006]]},"ISBN":["9783540354550","9783540354611"],"references-count":14,"URL":"https:\/\/doi.org\/10.1007\/11780441_16","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2006]]}}}