{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,27]],"date-time":"2026-05-27T15:47:58Z","timestamp":1779896878657,"version":"3.53.1"},"reference-count":35,"publisher":"Springer Science and Business Media LLC","issue":"4","license":[{"start":{"date-parts":[[2012,11,8]],"date-time":"2012-11-08T00:00:00Z","timestamp":1352332800000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2014,4]]},"DOI":"10.1007\/s00453-012-9708-5","type":"journal-article","created":{"date-parts":[[2012,11,7]],"date-time":"2012-11-07T17:30:41Z","timestamp":1352309441000},"page":"886-915","source":"Crossref","is-referenced-by-count":14,"title":["Constructing Minimal Phylogenetic Networks from Softwired Clusters is Fixed Parameter Tractable"],"prefix":"10.1007","volume":"68","author":[{"given":"Steven","family":"Kelk","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Celine","family":"Scornavacca","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2012,11,8]]},"reference":[{"issue":"3","key":"9708_CR1","doi-asserted-by":"crossref","first-page":"458","DOI":"10.1109\/tcbb.2007.1019","volume":"4","author":"M. Bordewich","year":"2007","unstructured":"Bordewich, M., Semple, C.: Computing the hybridization number of two phylogenetic trees is fixed-parameter tractable. IEEE\/ACM Trans. Comput. Biol. Bioinf. 4(3), 458\u2013466 (2007)","journal-title":"IEEE\/ACM Trans. Comput. Biol. Bioinf."},{"issue":"8","key":"9708_CR2","doi-asserted-by":"crossref","first-page":"914","DOI":"10.1016\/j.dam.2006.08.008","volume":"155","author":"M. Bordewich","year":"2007","unstructured":"Bordewich, M., Semple, C.: Computing the minimum number of hybridization events for a consistent evolutionary history. Discrete Appl. Math. 155(8), 914\u2013928 (2007)","journal-title":"Discrete Appl. Math."},{"key":"9708_CR3","doi-asserted-by":"crossref","first-page":"86","DOI":"10.1177\/117693430700300017","volume":"3","author":"M. Bordewich","year":"2007","unstructured":"Bordewich, M., Linz, S., John, K.St., Semple, C.: A reduction algorithm for computing the hybridization number of two trees. Evol. Bioinform. 3, 86\u201398 (2007)","journal-title":"Evol. Bioinform."},{"key":"9708_CR4","doi-asserted-by":"crossref","first-page":"372","DOI":"10.1109\/TCBB.2011.137","volume":"9","author":"Z.-Z. Chen","year":"2012","unstructured":"Chen, Z.-Z., Wang, L.: Algorithms for reticulate networks of multiple phylogenetic trees. IEEE\/ACM Trans. Comput. Biol. Bioinform. 9, 372\u2013384 (2012)","journal-title":"IEEE\/ACM Trans. Comput. Biol. Bioinform."},{"issue":"10","key":"9708_CR5","doi-asserted-by":"crossref","first-page":"1305","DOI":"10.1089\/cmb.2009.0166","volume":"18","author":"J. Collins","year":"2011","unstructured":"Collins, J., Linz, S., Semple, C.: Quantifying hybridization in realistic time. J. Comput. Biol. 18(10), 1305\u20131318 (2011)","journal-title":"J. Comput. Biol."},{"key":"9708_CR6","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. Springer, Berlin (1999)"},{"key":"9708_CR7","volume-title":"Parameterized Complexity Theory","author":"J. Flum","year":"2006","unstructured":"Flum, J., Grohe, M.: Parameterized Complexity Theory. Springer, Berlin (2006)"},{"key":"9708_CR8","doi-asserted-by":"crossref","first-page":"289","DOI":"10.1007\/978-3-642-02441-2_26","volume-title":"Proceedings of the 20th Annual Symposium on Combinatorial Pattern Matching, CPM \u201909","author":"P. Gambette","year":"2009","unstructured":"Gambette, P., Berry, V., Paul, C.: The structure of level-k phylogenetic networks. In: Proceedings of the 20th Annual Symposium on Combinatorial Pattern Matching, CPM \u201909, pp. 289\u2013300. Springer, Berlin (2009)"},{"key":"9708_CR9","volume-title":"Mathematics of Evolution and Phylogeny","year":"2005","unstructured":"Gascuel, O. (ed.): Mathematics of Evolution and Phylogeny. Oxford University Press, Oxford (2005)"},{"key":"9708_CR10","volume-title":"Reconstructing Evolution: New Mathematical and Computational Advances","year":"2007","unstructured":"Gascuel, O., Steel, M. (eds.): Reconstructing Evolution: New Mathematical and Computational Advances. Oxford University Press, Oxford (2007)"},{"issue":"1","key":"9708_CR11","doi-asserted-by":"crossref","first-page":"79","DOI":"10.1093\/comjnl\/bxm049","volume":"51","author":"J. Gramm","year":"2008","unstructured":"Gramm, J., Nickelsen, A., Tantau, T.: Fixed-parameter algorithms in phylogenetics. Comput. J. 51(1), 79\u2013101 (2008)","journal-title":"Comput. J."},{"issue":"10","key":"9708_CR12","doi-asserted-by":"crossref","first-page":"1247","DOI":"10.1089\/cmb.2006.0137","volume":"14","author":"D. Gusfield","year":"2007","unstructured":"Gusfield, D., Bansal, V., Bafna, V., Song, Y.: A decomposition theory for phylogenetic networks and incompatible characters. J. Comput. Biol. 14(10), 1247\u20131272 (2007)","journal-title":"J. Comput. Biol."},{"issue":"6\u20137","key":"9708_CR13","doi-asserted-by":"crossref","first-page":"806","DOI":"10.1016\/j.dam.2005.05.044","volume":"155","author":"D. Gusfield","year":"2007","unstructured":"Gusfield, D., Hickerson, D., Eddhu, S.: An efficiently computed lower bound on the number of recombinations in phylognetic networks: theory and empirical study. Discrete Appl. Math. 155(6\u20137), 806\u2013830 (2007)","journal-title":"Discrete Appl. Math."},{"key":"9708_CR14","doi-asserted-by":"crossref","first-page":"23","DOI":"10.1093\/gbe\/evq077","volume":"3","author":"D.H. Huson","year":"2011","unstructured":"Huson, D.H., Scornavacca, C.: A survey of combinatorial methods for phylogenetic networks. Genome Biol. Evol. 3, 23\u201335 (2011)","journal-title":"Genome Biol. Evol."},{"issue":"12","key":"9708_CR15","doi-asserted-by":"crossref","first-page":"i85","DOI":"10.1093\/bioinformatics\/btp217","volume":"25","author":"D.H. Huson","year":"2009","unstructured":"Huson, D.H., Rupp, R., Berry, V., Gambette, P., Paul, C.: Computing galled networks from real data. Bioinformatics 25(12), i85\u2013i93 (2009)","journal-title":"Bioinformatics"},{"key":"9708_CR16","volume-title":"Phylogenetic Networks: Concepts, Algorithms and Applications","author":"D.H. Huson","year":"2011","unstructured":"Huson, D.H., Rupp, R., Scornavacca, C.: Phylogenetic Networks: Concepts, Algorithms and Applications. Cambridge University Press, Cambridge (2011)"},{"key":"9708_CR17","series-title":"Lecture Notes in Bioinformatics","doi-asserted-by":"crossref","first-page":"265","DOI":"10.1007\/11415770_20","volume-title":"Research in Computational Molecular Biology (RECOMB)","author":"T.N.D. Huynh","year":"2005","unstructured":"Huynh, T.N.D., Jansson, J., Nguyen, N.B., Sung, W.-K.: Constructing a smallest refining galled phylogenetic network. In: Research in Computational Molecular Biology (RECOMB). Lecture Notes in Bioinformatics, vol. 3500, pp. 265\u2013280 (2005)"},{"issue":"1","key":"9708_CR18","doi-asserted-by":"crossref","first-page":"60","DOI":"10.1016\/j.tcs.2006.06.022","volume":"363","author":"J. Jansson","year":"2006","unstructured":"Jansson, J., Sung, W.-K.: Inferring a level-1 phylogenetic network from a dense set of rooted triplets. Theor. Comput. Sci. 363(1), 60\u201368 (2006)","journal-title":"Theor. Comput. Sci."},{"issue":"5","key":"9708_CR19","doi-asserted-by":"crossref","first-page":"1098","DOI":"10.1137\/S0097539704446529","volume":"35","author":"J. Jansson","year":"2006","unstructured":"Jansson, J., Nguyen, N.B., Sung, W.-K.: Algorithms for combining rooted triplets into a galled phylogenetic network. SIAM J. Comput. 35(5), 1098\u20131121 (2006)","journal-title":"SIAM J. Comput."},{"key":"9708_CR20","doi-asserted-by":"crossref","first-page":"517","DOI":"10.1109\/TCBB.2011.128","volume":"9","author":"S. Kelk","year":"2012","unstructured":"Kelk, S., Scornavacca, C., van Iersel, L.: On the elusiveness of clusters. IEEE\/ACM Trans. Comput. Biol. Bioinform. 9, 517\u2013534 (2012)","journal-title":"IEEE\/ACM Trans. Comput. Biol. Bioinform."},{"key":"9708_CR21","doi-asserted-by":"crossref","first-page":"375","DOI":"10.1093\/genetics\/163.1.375","volume":"163","author":"S.R. Myers","year":"2003","unstructured":"Myers, S.R., Griffiths, R.C.: Bounds on the minimum number of recombination events in a sample history. Genetics 163, 375\u2013394 (2003)","journal-title":"Genetics"},{"key":"9708_CR22","volume-title":"The Problem Solving Handbook for Computational Biology and Bioinformatics","author":"L. Nakhleh","year":"2009","unstructured":"Nakhleh, L.: Evolutionary phylogenetic networks: models and issues. In: The Problem Solving Handbook for Computational Biology and Bioinformatics. Springer, Berlin (2009)"},{"key":"9708_CR23","series-title":"Oxford Lecture Series in Mathematics and Its Applications","doi-asserted-by":"crossref","DOI":"10.1093\/acprof:oso\/9780198566076.001.0001","volume-title":"Invitation to Fixed Parameter Algorithms","author":"R. Niedermeier","year":"2006","unstructured":"Niedermeier, R.: Invitation to Fixed Parameter Algorithms. Oxford Lecture Series in Mathematics and Its Applications. Oxford University Press, Oxford (2006)"},{"key":"9708_CR24","volume-title":"Reconstructing Evolution\u2014New Mathematical and Computational Advances","author":"C. Semple","year":"2007","unstructured":"Semple, C.: Hybridization networks. In: Reconstructing Evolution\u2014New Mathematical and Computational Advances. Oxford University Press, Oxford (2007)"},{"key":"9708_CR25","doi-asserted-by":"crossref","DOI":"10.1093\/oso\/9780198509424.001.0001","volume-title":"Phylogenetics","author":"C. Semple","year":"2003","unstructured":"Semple, C., Steel, M.: Phylogenetics. Oxford University Press, Oxford (2003)"},{"key":"9708_CR26","series-title":"LNCS","first-page":"275","volume-title":"CPM09","author":"T.-H. To","year":"2009","unstructured":"To, T.-H., Habib, M.: Level-k phylogenetic networks are constructable from a dense triplet set in polynomial time. In: CPM09. LNCS, vol. 5577, pp. 275\u2013288 (2009)"},{"key":"9708_CR27","doi-asserted-by":"crossref","first-page":"207","DOI":"10.1007\/s00453-009-9333-0","volume":"60","author":"L. Iersel van","year":"2011","unstructured":"van Iersel, L., Kelk, S.: Constructing the simplest possible phylogenetic network from triplets. Algorithmica 60, 207\u2013235 (2011)","journal-title":"Algorithmica"},{"issue":"1","key":"9708_CR28","doi-asserted-by":"crossref","first-page":"245","DOI":"10.1016\/j.jtbi.2010.10.032","volume":"269","author":"L.J.J. Iersel van","year":"2011","unstructured":"van Iersel, L.J.J., Kelk, S.M.: When two trees go to war. J. Theor. Biol. 269(1), 245\u2013255 (2011)","journal-title":"J. Theor. Biol."},{"issue":"4","key":"9708_CR29","doi-asserted-by":"crossref","first-page":"667","DOI":"10.1109\/TCBB.2009.22","volume":"6","author":"L.J.J. Iersel van","year":"2009","unstructured":"van Iersel, L.J.J., Keijsper, J.C.M., Kelk, S.M., Stougie, L., Hagen, F., Boekhout, T.: Constructing level-2 phylogenetic networks from triplets. IEEE\/ACM Trans. Comput. Biol. Bioinform. 6(4), 667\u2013681 (2009)","journal-title":"IEEE\/ACM Trans. Comput. Biol. Bioinform."},{"issue":"2","key":"9708_CR30","doi-asserted-by":"crossref","first-page":"597","DOI":"10.1142\/S0219720009004308","volume":"7","author":"L.J.J. Iersel van","year":"2009","unstructured":"van Iersel, L.J.J., Kelk, S.M., Mnich, M.: Uniqueness, intractability and exact algorithms: reflections on level-k phylogenetic networks. J. Bioinform. Comput. Biol. 7(2), 597\u2013623 (2009)","journal-title":"J. Bioinform. Comput. Biol."},{"key":"9708_CR31","doi-asserted-by":"crossref","first-page":"i124","DOI":"10.1093\/bioinformatics\/btq202","volume":"26","author":"L.J.J. Iersel van","year":"2010","unstructured":"van Iersel, L.J.J., Kelk, S.M., Rupp, R., Huson, D.H.: Phylogenetic networks do not need to be complex: Using fewer reticulations to represent conflicting clusters. Bioinformatics 26, i124\u2013i131 (2010). Special issue: Proceedings of Intelligent Systems for Molecular Biology 2010 (ISMB2010), 10th\u201313th September (2010)","journal-title":"Bioinformatics"},{"key":"9708_CR32","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"390","DOI":"10.1007\/978-3-642-04241-6_32","volume-title":"Algorithms in Bioinformatics","author":"C. Whidden","year":"2009","unstructured":"Whidden, C., Zeh, N.: A unifying view on approximation and fpt of agreement forests. In: Salzberg, S., Warnow, T. (eds.) Algorithms in Bioinformatics. Lecture Notes in Computer Science, vol. 5724, pp. 390\u2013402. Springer, Berlin (2009)"},{"key":"9708_CR33","unstructured":"Whidden, C., Beiko, R.G., Zeh, N.: Fixed-parameter and approximation algorithms for maximum agreement forests. arXiv:1108.2664v1 [q-bio.PE]"},{"key":"9708_CR34","doi-asserted-by":"crossref","first-page":"i140","DOI":"10.1093\/bioinformatics\/btq198","volume":"26","author":"Y. Wu","year":"2010","unstructured":"Wu, Y.: Close lower and upper bounds for the minimum reticulate network of multiple phylogenetic trees. Bioinformatics 26, i140\u2013i148 (2010). Special issue: Proceedings of Intelligent Systems for Molecular Biology 2010 (ISMB2010), 10th\u201313th September (2010)","journal-title":"Bioinformatics"},{"issue":"3","key":"9708_CR35","doi-asserted-by":"crossref","first-page":"229","DOI":"10.1007\/s10878-007-9129-6","volume":"16","author":"Y. Wu","year":"2008","unstructured":"Wu, Y., Gusfield, D.: A new recombination lower bound and the minimum perfect phylogenetic forest problem. J. Comb. Optim. 16(3), 229\u2013247 (2008)","journal-title":"J. Comb. Optim."}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-012-9708-5.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00453-012-9708-5\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-012-9708-5","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,5,1]],"date-time":"2024-05-01T04:58:36Z","timestamp":1714539516000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00453-012-9708-5"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2012,11,8]]},"references-count":35,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2014,4]]}},"alternative-id":["9708"],"URL":"https:\/\/doi.org\/10.1007\/s00453-012-9708-5","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[2012,11,8]]}}}